No.1

题目

平衡二叉树

思路

• 递归法
• 在遍历中比较左右子树的高度差

递归分析

1. 参数：当前传入节点。 返回值：以当前传入节点为根节点的树的高度
2. 那么如何标记左右子树是否差值大于1呢？可以返回-1 来标记已经不符合平衡树的规则了
3. 明确终止条件：递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0
4. 明确单层递归的逻辑：分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。

代码

public int getHeight(TreeNode node) {  
    if (node == null)  
        return 0;  
  
    // 左树高度  
    int leftTreeHeight = getHeight(node.left);  
    // 右树高度  
    int rightTreeHeight = getHeight(node.right);  
  
    // 假如发现子树已经不平衡，没有意义再继续比较  
    // 直接返回-1，迅速通过所有的递归过程  
    // 之后所有的递归调用结果都是-1  
    if (leftTreeHeight == -1 || rightTreeHeight == -1)  
        return -1;  
  
    int diffHeight = Math.abs(leftTreeHeight - rightTreeHeight);  
    if (diffHeight <= 1)  
        return 1 + Math.max(leftTreeHeight, rightTreeHeight);  
    else  
        return -1;  
}  
  
public boolean isBalanced(TreeNode root) {  
    if (root == null)  
        return true;  
  
    return getHeight(root) != -1;  
}

No.2

题目

二叉树的所有路径

思路

• 递归
• 回溯
• 中，中为什么写在最前面？因为最后一个节点也要加入到path中
  • 不这样写的话，访问叶子节点时，会直接取用nodePath拿来构建路径，这时候该节点还没被更新到nodePath种

递归过程

1. 参数：节点+存放节点访问路径的列表+存放结果的列表
2. 返回值：无
3. 终止逻辑：访问到叶子节点，以规定形式存放访问路径
4. 单层递归内部逻辑：前序遍历，子节点非空才进入，退出访问子节点递归后，须回溯

代码

public void traverse(TreeNode node, List<Integer> nodePath, List<String> result) {  
    // preOrder traverse  
    nodePath.add(node.val); // mid  
  
    // node会为null吗?  
    if (node.left == null && node.right == null) {  
        StringBuilder sb = new StringBuilder();  
        for (Integer item : nodePath) {  
            sb.append(item);  
            sb.append("->");  
        }  
        sb.deleteCharAt(sb.length() - 1);  
        sb.deleteCharAt(sb.length() - 1);  
        result.add(sb.toString());  
        return;    
    }  
  
    // 防止空节点进入nodePath  
    if (node.left != null) { // left  
        traverse(node.left, nodePath, result);  
        nodePath.remove(nodePath.size() - 1);  
    }  
    if (node.right != null) { // right  
        traverse(node.right, nodePath, result);  
        nodePath.remove(nodePath.size() - 1);  
    }  
}  
  
public List<String> binaryTreePaths(TreeNode root) {  
    List<Integer> nodePath = new ArrayList<>();  
    List<String> result = new ArrayList<>();  
    traverse(root, nodePath, result);  
  
    return result;  
}

No.3

题目

思路

• 递归法
• 左叶子只能通过父节点去判断

递归分析

1. 参数：节点，返回值：子树左叶子值之和
2. 终止逻辑：找到了左叶子
3. 单层递归处理逻辑：后序遍历，等待左右子树结果返回后相加

代码

public void findLeftLeaves(TreeNode node, List<Integer> leftList) {
	// node不会为null
    if (node.left != null && node.left.left == null && node.left.right == null) {  
        leftList.add(node.left.val);  
    }  
  
    if (node.left != null)  
        findLeftLeaves(node.left, leftList);  
    if (node.right != null)  
        findLeftLeaves(node.right, leftList);  
	// 无需处理中间节点
}  
  
public int sumOfLeftLeaves(TreeNode root) {  
    List<Integer> leftLeafList = new ArrayList<>();  
    findLeftLeaves(root, leftLeafList);  
  
    int result = 0;  
    for (Integer integer : leftLeafList) {  
        result += integer;  
    }  
  
    return result;  
}