leetcode_day17

今日内容：

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

平衡二叉树

只是判断平衡二叉树，比较简单，按规范化思路来吧，避免一会有感觉秒了，一会没感觉卡了

递归结束条件：如果左子树不是平衡二叉树 或者 右子树不是平衡二叉树 或者 左右子树深度差距大于1

递归操作：判断左子树是不是平衡二叉树，判断右子树是不是平衡二叉树，获取左右子树深度

参数及返回值：根节点 + 是否合法的bool值

bool isBalanced(TreeNode* root) {
    if(root == nullptr) return true;//空视作平衡
    if(isBalanced(root->left) && isBalanced(root->right)) {//左右都是
        return abs(getDepth(root->left) - getDepth(root->right)) <= 1;//左右深度是否匹配
    }
    else return false;
}
int getDepth(TreeNode * root) {
    if(root == nullptr) return 0;//空树深度0
    int ans = 1;
    return max(getDepth(root->left), getDepth(root->right)) + 1;//左右子树最大深度加自己
}

这个时间复杂度较大，\(O(n^2)\)，对每一个节点都要单独求深度然后判断，自顶向下

自底向上做法：

bool isBalanced(TreeNode* root) {
    if(root == nullptr) return true;
    return getDepth(root) != -1;
}
int getDepth(TreeNode * root) {
    if(root == nullptr) return 0;
    int left = getDepth(root->left);
    if(left == -1) return -1;//只要一个子树不平衡，整个树就不平衡
    int right = getDepth(root->right);
    if(right == -1) return -1;
    return abs(left - right) <= 1 ? max(left, right) + 1 : -1;
}

二叉树的所有路径

递归三步：

1. 参数&返回值

无需返回值，参数有根节点和存路径和答案的数组

2. 递归终止条件

遇到叶节点

3. 递归逻辑

没遇到就接着往里插

比较简单，贴代码：

class Solution {
public:
    vector<string> ans;
    vector<string> binaryTreePaths(TreeNode* root) {
        if(!root) return {};
        string line;
        traversal(root, line);
        return ans;
    }
    void traversal(TreeNode * root, string s) {
        s += to_string(root->val);
        if(!root->left && !root->right) ans.push_back(s);
        else {
            s += "->";
            if(root->left) traversal(root->left, s);
            if(root->right) traversal(root->right, s);
        }
    }
};

迭代写法

用一个栈存节点，一个栈存目前已经走过的路径 注意push根节点和其他节点的差异

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        if(!root) return ans;
        stack<string> path;
        stack<TreeNode *> st;
        st.push(root);
        path.push(to_string(root->val));//only value
        while(!st.empty()) {
            TreeNode * cur = st.top(); st.pop();
            string tem = path.top(); path.pop();

            if(cur->left) {
                st.push(cur->left);
                path.push(tem + "->" + to_string(cur->left->val));//insert the next value
            }
            if(cur->right) {
                st.push(cur->right);
                path.push(tem + "->" + to_string(cur->right->val));
            }
            if(!cur->left && !cur->right) {//no next value
                ans.push_back(tem);
            }
        }
        return ans;
    }
};

左叶子之和

需要注意，单独一个根节点不能称作左叶子，只是叶子，但不左

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(!root) return 0;
        int ans = 0;
        if(root->left && !root->left->left && !root->left->right) {
            ans = root->left->val;
        }
        return ans + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
};

这个递归看得有点懵，后面再来仔细理解一下吧