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

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

文章链接：代码随想录平衡二叉树        代码随想录二叉树的所有路径        代码随想录左叶子之和

视频链接：代码随想录平衡二叉树        代码随想录二叉树的所有路径        代码随想录左叶子之和

目录

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

1. LeetCode 110. 平衡二叉树

1.1 思路

1.2 代码

2. LeetCode 257. 二叉树的所有路径

2.1 思路

2.2 代码

3. LeetCode 404. 左叶子之和

3.1 思路

3.2 代码

---

 

1. LeetCode 110. 平衡二叉树

1.1 思路

1. 平衡二叉树：任何节点的左右子树的高度差小于等于1
2. 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。求深度按道理应该是前序遍历
3. 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。求高度按道理应该是后序遍历
4. 递归函数的参数和返回值：返回值是高度，参数是TreeNode。这里注意我们判断任何一个节点的左右子树的高度差时，如果发现高度差大于1了返回时就返回-1，就告诉上一层这棵树已经不是平衡的了，一个节点一个节点的往上返回，最后告诉根节点不是平衡的
5. 终止条件：如果节点为空就返回0，空节点是没有高度的
6. 单层递归的逻辑：左子树int leftHeight=getHeight(node.left); 如果左子树高度==-1，那就往上返回-1；右子树int rightHeight=getHeight(node.right); 如果右子树高度==-1，那就往上返回-1；如果左右子树都符合平衡的条件，那就判断高度差，int result=（左子树-右子树）的高度差的绝对值，如果大于1了，那就不符合，往上返回-1；如果不是，说明就符合条件了，那就返回 左子树和右子树之间的最大值+1 ，这个值就是基于左子树和右子树的高度的父节点的高度
7. 以上采用的是后序遍历

1.2 代码

class Solution {
   /**
     * 递归法
     */
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
 
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        // 左右子树高度差大于1，return -1表示已经不是平衡树了
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

2. LeetCode 257. 二叉树的所有路径

2.1 思路

1. 我们求路径的过程中使用前序遍历，为什么？因为这样我们才能让父节点指向孩子节点，这样才能按照路径的方式输出
2. 这题递归就不得不提回溯，为什么有回溯？递归和回溯其实是相辅相成的，有递归就一定有回溯。那么这题为什么有回溯的过程呢？当我们用集合收集到一个路径以后就要把对应遍历过的元素回弹，这个过程就是一个回溯的过程
3. 递归函数的参数和返回值：参数TreeNode，Listpath，Listresult，path集合存的是单条路径，result存的是所有的路径。我们直接添加到集合就不需要返回值了
4. 终止条件：我们遍历到的节点左右孩子都为空就说明到了叶子节点，就是收获结果的时候，这时result.add(path)，这里需要把int类型的数据之间添加“->”转化为String，符合LeetCode的要求，然后return
5. 单层处理逻辑：前序遍历“根左右”，处理过程就是要把路径的值添加到path中，但这里注意！我们处理“根”要在终止条件之前，path.add(node.val)。因为如果“根”写在终止条件以下，就会把叶子节点落下，因为直接return了。然后是“左”，向左遍历时（向右也是），要判断一下node.left是否为空，不为空才去遍历，避免终止条件上发生空指针异常，判断之后就递归函数(node.left, path, result)，然后就是回溯
6. 回溯的处理逻辑：path.remove(path.size() - 1)，这里是把刚加入的元素弹出了。这里回溯的解释看视频讲解
7. 然后到“右”，右孩子不为空才遍历，递归函数(node.right, path, result)

2.2 代码

//解法一
 
//方式一
class Solution {
    /**
     * 递归法
     */
    public List binaryTreePaths(TreeNode root) {
        List res = new ArrayList<>();// 存最终的结果
        if (root == null) {
            return res;
        }
        List paths = new ArrayList<>();// 作为结果中的路径
        traversal(root, paths, res);
        return res;
    }
 
    private void traversal(TreeNode root, List paths, List res) {
        paths.add(root.val);// 前序遍历，中
        // 遇到叶子结点
        if (root.left == null && root.right == null) {
            // 输出
            StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串，速度更快
            for (int i = 0; i < paths.size() - 1; i++) {
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));// 记录最后一个节点
            res.add(sb.toString());// 收集一个路径
            return;
        }
        // 递归和回溯是同时进行，所以要放在同一个花括号里
        if (root.left != null) { // 左
            traversal(root.left, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
        if (root.right != null) { // 右
            traversal(root.right, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
    }
}

3. LeetCode 404. 左叶子之和

3.1 思路

1. 注意判断什么是左叶子，不要误解题目意思
2. 这道题与以往不同，我们要找到的左叶子不能够遍历到它的时候才获取，因为这样只能知道它是不是叶子节点，但不知道是不是左叶子。因此我们要遍历到它的父节点的时候就判断左叶子。判断条件：左孩子不为空并且左孩子的左右孩子同时为空。符合条件才是我们要的左叶子
3. 这题用后序遍历挺符合思路的，因为一层一层返回给上一层，父节点只要加上左子树的左叶子和右子树的左叶子即可
4. 递归函数的参数和返回值：参数是TreeNode，返回值int。但这题不用额外定义函数了，直接用力扣的主函数即可
5. 终止条件：第一个肯定是如果节点为空就返回0；第二个就是遇到叶子节点（左右孩子军为空）就返回0；这里是因为叶子节点我们要的是收集左子树和右子树的左叶子之和，都为空说明为0，因为左子树的左叶子为0，右子树的左叶子也为0
6. 单层递归逻辑：int leftVal=函数(root.left)。int rightVal=函数(root.right)。判断条件：左孩子不为空并且左孩子的左右孩子同时为空，符合条件就进入leftVal=root.left.val 。int sum=leftVal+rightVal。然后return sum即可

3.2 代码

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int leftValue = sumOfLeftLeaves(root.left);    // 左
        int rightValue = sumOfLeftLeaves(root.right);  // 右
                                                       
        int midValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) { 
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;  // 中
        return sum;
    }
}