算法训练营day17

一、平衡二叉树

参考链接110. 平衡二叉树 - 力扣（LeetCode）

后序遍历+“剪枝”

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if (left == -1) return -1; //剪枝
        int right = recur(root.right);
        if (right == -1) return -1; //剪枝
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二、二叉树的所有路径

dfs深度优先搜索

class Solution {
    //维护一个字符串列表res，用于存储总结果路径
    List<String> res = new ArrayList<>();
    //使用名为path的StringBuilder来构建当前路径
    StringBuilder path = new StringBuilder();

    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root);
        return res;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;
		
        //将当前路径的长度保存在变量中
        int curLen = path.length();
        //将当前值附加到path中
        path.append(root.val);
        
        // *终止条件：当左右子树都为空的时候，将结果加入到res中并返回
        if (root.left == null && root.right == null)
            res.add(path.toString());
        
        path.append("->");
        //进行dfs左右递归
        dfs(root.left);
        dfs(root.right);
        path.delete(curLen, path.length());
//t 是在递归调用dfs方法之前path的长度，即在当前层级下添加新节点之前的path长度
//path.length() 返回当前path的长度，即在递归调用dfs后path的长度
//当前这步删除的是当前节点处理的值及向下的子路径从path中删除
//以便正确处理下一个节点或回溯到上一个结点时重新构建正确的路径
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

三、左叶子之和

重点是搞清楚左叶子的定义：

节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点

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;
    }
}
       int sum = midValue + leftValue + rightValue;  // 中
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18