代码随想录算法训练营第十七天|110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和

文档链接：https://programmercarl.com/

LeetCode110.平衡二叉树

题目链接：https://leetcode.cn/problems/balanced-binary-tree/

思路：

这里强调一波概念：

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

后序遍历：

class Solution {
public:
    int getHeight(TreeNode* node) {
        if(node == NULL) return 0;
        int leftHeight = getHeight(node->left);
        if(leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if(rightHeight == -1) return -1;
        int height;
        if(abs(leftHeight - rightHeight) > 1) return -1;
        else height = max(leftHeight, rightHeight) + 1;
        return height;
    }
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        if(getHeight(root) == -1) return false;
        else return true;
    }
};

LeetCode257.二叉树的所有路径

题目链接：https://leetcode.cn/problems/binary-tree-paths/

思路：第一次接触递归，有点懵，感觉很神奇。

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。回溯和递归是一一对应的，有一个递归，就要有一个回溯

前序遍历+回溯：

class Solution {
public:
    void traversal(TreeNode* node, vector<int>& path, vector<string>& result) {
        path.push_back(node->val);
        if(node->left == NULL && node->right == NULL) {
            string sPath;
            for(int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        if(node->left) {
            traversal(node->left, path, result);
            path.pop_back();
        }
        if(node->right) {
            traversal(node->right, path, result);
            path.pop_back();
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<int> path;
        vector<string> result;
        if(root == NULL) return result;
        traversal(root, path, result);
        return result;

    }
};

LeetCode404.左叶子之和

题目链接：https://leetcode.cn/problems/sum-of-left-leaves/

思路：

首先要注意是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历。

因为题目中其实没有说清楚左叶子究竟是什么节点，那么我来给出左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点

那么判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。

后序遍历：

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

总结：总算追上进度了，但是质量感觉落下了。迭代法没看不说，递归法掌握的也不是很好，递归三部曲我懂，一到自己写的时候，具体细节方面总还是会出错。慢慢来吧！