No.1

题目

找树左下角的值

思路

• 队列，层序遍历
• Deque既可以用作栈也可以用作队列，谨慎使用

代码

public int findBottomLeftValue(TreeNode root) {  
    Queue<TreeNode> queue = new LinkedList<>();  
    queue.add(root);  
    int result = 0; // 记录最后一行第一个元素  
  
    while (!queue.isEmpty()) {  
        int levelSize = queue.size();  
        for (int i = 0; i < levelSize; i++) {  
            TreeNode temp = queue.poll();  
            if (i == 0)  
                result = temp.val;  
            if (temp.left != null) {  
                queue.add(temp.left);  
            }  
            if (temp.right != null) {  
                queue.add(temp.right);  
            }  
        }  
    }  
  
    return result;  
}

No.2

题目

路径总和

思路

• 递归
• 注意：非子结点curVal >= targetSum就一定没有必要寻找了吗？不见得，可能有负数的节点值

递归思路

1. 返回值：boolean，参数：节点，当前路径值，target
2. 终止逻辑：当前节点是叶子节点，发现当前路径值等于target，返回true；当前节点不是叶子节点，但路径值已经大于等于target，返回false；
3. 单层逻辑：前序遍历，对中间节点没有操作，若存在左右节点，则递归访问左右节点。return 递归方法（左节点）||递归方法（右节点）

代码

public boolean pathSum(TreeNode node, int curVal, int targetSum) {
    if (node.left == null && node.right == null) { // 子节点  
        return curVal == targetSum;  
    }  
  
    boolean leftTree = false;  
    boolean rightTree = false;  
  
    if (node.left != null)  
        leftTree = pathSum(node.left, curVal + node.left.val, targetSum);  
    if (node.right != null)  
        rightTree = pathSum(node.right, curVal + node.right.val, targetSum);  
  
    return leftTree || rightTree;  
}  
  
public boolean hasPathSum(TreeNode root, int targetSum) {  
    if (root == null)  
        return false;  
  
    return pathSum(root, root.val, targetSum);  
}

No.3 ==

题目

从中序与后序遍历序列构造二叉树

思路

• 递归
• 模拟推导的过程

递归分析

代码

public TreeNode build(int[] inorder, int in_left, int in_right, int[] postorder, int post_left, int post_right, Map<Integer, Integer> inorderMap) {  
    // [left, right)  
    // 没有节点了，返回空  
    if (post_left == post_right)  
        return null;  
  
    // 从后序数组中取出最后一个元素，就是根  
    int rootVal = postorder[post_right - 1];  
    TreeNode root = new TreeNode(rootVal);  
  
    // 叶子节点  
    if (post_right - post_left == 1)  
        return root;  
  
    // 找切割点  
    int cutIndex = inorderMap.get(rootVal);  
  
    // 切割inorder，得到inorder左数组和inorder右数组  
    // 利用inorder和postorder数组的大小必定相等特性，切割postorder，得到postorder左数组和postorder右数组  
    root.left = build(inorder, in_left, cutIndex, postorder, post_left, post_left + (cutIndex - in_left), inorderMap);  
    root.right = build(inorder, cutIndex + 1, in_right, postorder, post_left + (cutIndex - in_left), post_right - 1, inorderMap);  
  
    return root;  
}  
  
public TreeNode buildTree(int[] inorder, int[] postorder) {  
    Map<Integer, Integer> inorderMap = new HashMap<>();  
    for (int i = 0; i < inorder.length; i++) {  
        inorderMap.put(inorder[i], i);  
    }  
  
    return build(inorder, 0, inorder.length, postorder, 0, postorder.length, inorderMap);  
}