二叉树|110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和

110.平衡二叉树

自己审题思路

判断二叉树左右子树的高度

看完代码随想录题解后的收获

基本一致

代码：

class Solution {
public:
    int getHeigh(TreeNode* cur) {
        if(cur == nullptr) return 0;

        int leftHeigh = getHeigh(cur->left);
        if(leftHeigh == -1) return -1;
        int rightHeigh = getHeigh(cur->right);
        if(rightHeigh == -1) return -1;

        if(abs(rightHeigh - leftHeigh) > 1) return -1;

        return 1 + max(leftHeigh, rightHeigh);
    }
    bool isBalanced(TreeNode* root) {
        return getHeigh(root) != -1;
    }
};

参考详解

257. 二叉树的所有路径

自己审题思路

遍历到叶子节点时保存路径。

看完代码随想录题解后的收获

理解回溯算法。

代码：

class Solution {
public:
    void traversal(TreeNode* cur, string path, vector<string>& result) {
        if(cur == nullptr) return;
        path += to_string(cur->val);

        if(cur->left ==  nullptr && cur->right == nullptr) {
            result.push_back(path); return;
        }

        if(cur->left) {
            traversal(cur->left, path + "->", result);
        }

        if(cur->right) {
            traversal(cur->right, path + "->", result);
        }

        return;

    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        traversal(root, path, result);
        return result;
    }
};

参考详解

404.左叶子之和

自己审题思路

找到叶子节点，然后累加

看完代码随想录题解后的收获

递归思路

代码：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == nullptr) return 0;
        if(root->left == nullptr && root->right == nullptr) return 0;

        int leftLeaves = sumOfLeftLeaves(root->left);
        if(root->left && !root->left->left && !root->left->right){
            leftLeaves = root->left->val;
        }
        int rightLeaves = sumOfLeftLeaves(root->right);
        return leftLeaves + rightLeaves;

    }
};
// class Solution {
// public:
//     int sumOfLeftLeaves(TreeNode* root) {
//         if (root == NULL) return 0;
//         if (root->left == NULL && root->right== NULL) return 0;

//         int leftValue = sumOfLeftLeaves(root->left);    // 左
//         if (root->left && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况
//             leftValue = root->left->val;
//         }
//         int rightValue = sumOfLeftLeaves(root->right);  // 右

//         int sum = leftValue + rightValue;               // 中
//         return sum;
//     }
// };

代码2：

class Solution {
public:
    void leftLeaves(TreeNode* cur, vector<int>& ans) {
        if(cur->left == nullptr && cur->right == nullptr) return;

        if(cur->left && !cur->left->left && !cur->left->right) {
            ans.push_back(cur->left->val);
        }
        if(cur->left)leftLeaves(cur->left, ans);
        if(cur->right)leftLeaves(cur->right, ans);
        return;
    }

    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) return 0;
        vector<int> ans;
        int sum = 0;
        leftLeaves(root, ans);

        for(int& num : ans) {
            sum += num;
        }
        return sum;
    }
};

参考详解