【LeetCode】day15：110 - 平衡二叉树, 257 - 二叉树的所有路径, 404 - 左叶子之和, 222 - 完全二叉树的节点个数

110.平衡二叉树

题目描述：

给定一个二叉树，判断它是否是 平衡二叉树

平衡二叉树的定义是，对于树中的每个节点，其左右子树的高度差不超过1。思路使用递归，对比左子树和右子树的高度差是否超过1，若超过1则当前节点返回-1作为标示，否则返回当前节点的最大深度。代码如下：

class Solution {
private:
    int traverse(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftHeight = traverse(root->left);
        int rightHeight = traverse(root->right);
        if (leftHeight == -1 || rightHeight == -1) {
            return -1;
        }
        if (leftHeight - rightHeight > 1 || leftHeight - rightHeight < -1) {
            return -1;
        }
        return max(leftHeight, rightHeight) + 1;
    }

public:
    bool isBalanced(TreeNode* root) {
        int height = traverse(root);
        if (height == -1) return false;
        return true;
    }
};

257.二叉树的所有路径

题目描述：

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。

主要思路为对树进行遍历并将遍历时的当前路径记录，并在到达叶子节点后将当前路径添加到结果中。同时在遍历过程中需要对路径的状态实时进行回溯，比如从当前节点退出，上一个节点的路径中就不应再保留当前节点的信息。这里使用字符串值传递方式，可以非显式的实现回溯。代码如下：

class Solution {
private:
    void traverse(TreeNode* root, string path, vector<string>& paths) {
        if (root == nullptr) return;
        if (!path.empty()) path += "->";
        path += to_string(root->val);
        if (!root->left && !root->right) {
            paths.push_back(path);
            return;
        }
        traverse(root->left, path, paths);
        traverse(root->right, path, paths);
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if (root == nullptr) return res;
        traverse(root, "", res);
        return res;
    }
};

另外使用迭代法进行遍历时，原理相同，在push节点进入记录节点的stack时同时将当前路径同时push进入记录路径的stack中，这样在每次循环获取当前节点时获取到的路径是对应的。注意在分别对左右节点的路径修改时，由于存在需要在处理前一个之后继续处理后一个的情况（左右节点都不为nullptr），所以不能修改path变量而是应该通过临时变量记录路径并入栈。代码如下：

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if (root == nullptr) return res;
        stack<TreeNode*> nodeStk;
        stack<string> pathStk;
        nodeStk.push(root);
        pathStk.push(to_string(root->val));
        while (!nodeStk.empty()) {
            TreeNode* cur = nodeStk.top(); nodeStk.pop();
            string path = pathStk.top(); pathStk.pop();
            if (!cur->left && !cur->right) {
                res.push_back(path);
                continue;
            }
            if (cur->left) {
                nodeStk.push(cur->left);
                pathStk.push(path + "->" + to_string(cur->left->val));
            }
            if (cur->right) {
                nodeStk.push(cur->right);
                pathStk.push(path + "->" + to_string(cur->right->val));
            }
        }
        return res;
    }
};

404.左叶子之和

题目描述：

给定二叉树的根节点 root ，返回所有左叶子之和。
示例 1：

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例 2:
输入: root = [1]
输出: 0

在遍历时使用isLeft的bool变量标示当前节点是否是上一个状态的左节点，在确认叶子节点值时同时需要确保该bool变量为true，其余均为遍历框架。代码如下：

class Solution {
private:
    int traverse(TreeNode* root, bool isLeft) {
        if (root == nullptr) return 0;
        if (!root->left && !root->right && isLeft) {
            return root->val;
        }
        int left = traverse(root->left, true);
        int right = traverse(root->right, false);
        return left + right;
    }

public:
    int sumOfLeftLeaves(TreeNode* root) {
        return traverse(root, false);
    }
};

同理可以使用迭代法，通过确认左节点的方式：若左节点不为nullptr且为叶子节点，则记录结果，除此之外的所有都不算左叶子。代码如下：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) return 0;
        stack<TreeNode*> stk;
        stk.push(root);
        int res = 0;
        while (!stk.empty()) {
            TreeNode* cur = stk.top(); stk.pop();
            // 若左节点不为nullptr且为叶子节点
            if (cur->left && !cur->left->left && !cur->left->right) {
                res += cur->left->val;
            }
            if (cur->left) stk.push(cur->left);
            if (cur->right) stk.push(cur->right);
        }
        return res;
    }
};

222.完全二叉树的节点个数

题目描述：

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 $1$~$2^h$ 个节点。
示例 1：

输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1

最简单的二叉树遍历计算节点数，这里使用层序遍历实现：

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> q;
        int res = 0;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            res += size;
            while (size--) {
                TreeNode* cur = q.front(); q.pop();
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
        }
        return res;
    }
};

由于题中所给为完全二叉树，可以根据其特性进行优化：完全二叉树的高度可以通过一直向左直到叶子节点确定、完全二叉树的节点树可以通过比较左右子树的高度来判断。
若左子树高度等于右子树，根据完全二叉树的性质可知左子树为满二叉树（完全二叉树的叶子节点从最左边开始，右子树高度相同则表示左边排满了）；若高度不同相反则表示左子树不满，而右子树一定是高度小一行的满二叉树。代码如下：

class Solution {
private:
    int getHeight(TreeNode* node) {
        int res = 0;
        while (node) {
            ++res;
            node = node->left;
        }
        return res;
    }

public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);
        if (leftHeight == rightHeight) {
            return (1 << leftHeight) + countNodes(root->right);
        } else {
            return (1 << rightHeight) + countNodes(root->left);
        }
    }
};