代码随想录day15 110.平衡二叉树 、257. 二叉树的所有路径 、404.左叶子之和 、222.完全二叉树的节点个数

代码随想录day15 110.平衡二叉树 、257. 二叉树的所有路径 、404.左叶子之和 、222.完全二叉树的节点个数

110. 平衡二叉树

这题对我比较困难的点是在于如何同时携带高度信息和是否是平衡二叉树的信息，卡哥则用了一个比较好的方法就是如果不是直接返回-1，则无需再求高度，以后可以借鉴这种想法

class Solution {
public:
    int getHeight(TreeNode* cur) {
        if (cur == nullptr) {
            return 0;
        }
        int leftHeight = getHeight(cur->left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = getHeight(cur->right);
        if (rightHeight == -1) {
            return -1;
        }
        if (abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return 1 + max(leftHeight, rightHeight);
    }

    bool isBalanced(TreeNode* root) {
        return getHeight(root) != -1;
    }
};

257. 二叉树的所有路径

挺简单的，可以很快写出来

class Solution {
public:
    vector<string> res;

    void getPath(TreeNode *cur, string path) {
        path += to_string(cur->val);
        if (cur->left == nullptr && cur->right == nullptr) {
            res.push_back(path);
            return;
        }
        path += "->";
        if (cur->left) {
            getPath(cur->left, path);
        }
        if (cur->right) {
            getPath(cur->right, path);
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        getPath(root, "");
        return res;
    }
};

404. 左叶子之和

挺简单的，可以很快写出来

class Solution {
public:

    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int sum = 0;
        if (root->left && root->left->left == nullptr && root->left->right == nullptr) {
            sum += root->left->val;
        }
        sum += sumOfLeftLeaves(root->left);
        sum += sumOfLeftLeaves(root->right);
        return sum;
    }
};

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

方法很巧，就是单层递归时判断个数时先判断是否为满二叉树，如果是就直接返回 2 ^ h - 1 ，注意右移表达为(1 << h) - 1，如果不是则再用左右子树递归和加一

class Solution {
public:
    int countNodes(TreeNode* root) {
        int leftDepth = 0;
        TreeNode *cur = root;
        while (cur) {
            leftDepth++;
            cur = cur->left;
        }
        cur = root;
        int rightDepth = 0;
        while (cur) {
            rightDepth++;
            cur = cur->right;
        }
        if (rightDepth == leftDepth) {
            return (1 << leftDepth) - 1;
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};