算法|找树左下角的值、路径总和、从中序与后序遍历序列构造二叉树、

一、 513. 找树左下角的值

题目链接：https://leetcode.cn/problems/find-bottom-left-tree-value/
思路一：使用前序遍历，达到叶子节点，即root.left == null && root.right == null,根据深度depth更新最大的结果

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int maxDepth = Integer.MIN_VALUE;
    private int result;
    private void findBottomLeftValue(TreeNode root, int depth){
        //到了叶子节点，更新结果
        if (root.left == null && root.right == null) {
            if (maxDepth < depth) {
                maxDepth = depth;
                result = root.val;
            }
            return;
        }
        if (root.left != null) {
            depth++;
            findBottomLeftValue(root.left, depth);
            depth--;
        }

        if (root.right != null) {
            depth++;
            findBottomLeftValue(root.right, depth);
            depth--;
        }
    }
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return 0;
        findBottomLeftValue(root, 0);
        return result;
    }
}

思路二：使用层序遍历，当 if (i == 0) 更新结果

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return 0;
        int result = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = queue.poll();
                if (i == 0) {
                    result = treeNode.val;
                }
                if (treeNode.left != null) queue.offer(treeNode.left);
                if (treeNode.right != null) queue.offer(treeNode.right);
            }
        }
        return result;
    }
}

二、112. 路径总和

题目链接：https://leetcode.cn/problems/path-sum/
思路一：使用前序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }

        if (root.left != null) {
            if (hasPathSum(root.left, targetSum - root.val)) return true;
        }
        if (root.right != null) {
            if (hasPathSum(root.right, targetSum - root.val)) return true;
        }
        return false;
    }
}

思路二、前序迭代法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        Stack<TreeNode> stackNode = new Stack<>();
        stackNode.push(root);
        Stack<Integer> stackSum = new Stack<>();
        stackSum.push(root.val);
        while (!stackNode.isEmpty()) {
            TreeNode treeNode = stackNode.pop();
            int sum = stackSum.pop();
            if (treeNode.left == null && treeNode.right == null && targetSum == sum) return true;
            if (treeNode.right != null) {
                stackNode.push(treeNode.right);
                stackSum.push(sum + treeNode.right.val);
            }
            if (treeNode.left != null) {
                stackNode.push(treeNode.left);
                stackSum.push(sum + treeNode.left.val);
            }
        }
        return false;
    }
}

三、 113. 路径总和 II

题目链接：https://leetcode.cn/problems/path-sum-ii/
思路一：前序遍历，到达叶子节点即 root.left == null && root.right == null 判断是否符合条件，符合条件加入到结果集中

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private void pathSum(TreeNode root, int targetSum, List<Integer> paths, List<List<Integer>> result) {
        paths.add(root.val);
        if (root.left == null && root.right == null) {
            if (targetSum == root.val) {
                result.add(new ArrayList<Integer>(paths));
            }      
            return;
        }
        if (root.left != null) {
            pathSum(root.left, targetSum - root.val, paths, result);
            paths.remove(paths.size() - 1);
        }

        if (root.right != null) {
            pathSum(root.right, targetSum - root.val, paths, result);
            paths.remove(paths.size() - 1);
        }

    }
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<Integer> paths = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        pathSum(root, targetSum, paths, result);
        return result;
    }
}

思路二：使用两个栈，一个栈存放treeNode 一个栈放new Object[]{'节点值列表'，‘到该节点的和’}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stackNode = new Stack<>();
        stackNode.push(root);
        Stack<Object[]> stackSum = new Stack<>();
        stackSum.push(new Object[] {root.val + "", root.val});
        while (!stackNode.isEmpty()) {
            TreeNode treeNode = stackNode.pop();
            Object  values[] = stackSum.pop();
            if (treeNode.left == null && treeNode.right == null) {
                //搜集结果
                if (targetSum == (int)values[1]) {
                    System.out.print(((String)values[0]));
                    System.out.println();
                    String paths[] = ((String)values[0]).split(",");
                    List<Integer> list = new ArrayList<>();
                    for (String path:paths) {
                        list.add(Integer.parseInt(path));
                    }
                    result.add(list);
                }
                continue;
            }
            if (treeNode.right != null) {
                stackNode.push(treeNode.right);
                stackSum.push(new Object[]{((String)values[0]) + "," + treeNode.right.val,  (int)values[1] + treeNode.right.val});
            }
            if (treeNode.left != null) {
                stackNode.push(treeNode.left);
                stackSum.push(new Object[]{((String)values[0]) + "," + treeNode.left.val, (int)values[1] + treeNode.left.val});
            }
        }
        return result;
    }
}

四、106. 从中序与后序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private HashMap<Integer, Integer> hashMap = new HashMap<>();
    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart >= inEnd || postStart > postEnd) return null;
        //后序中最后一个元素，是中序的root
        int val = postorder[postEnd - 1];
        //在中序的切割点索引
        int inIndex = hashMap.get(val);
        //中序列表中分割点到inStart的差值，主要用于切割后序
        int inLeft = inIndex - inStart;
        TreeNode root = new TreeNode(val);
        root.left = buildTree(inorder, inStart, inIndex, postorder, postStart, postStart + inLeft);
        root.right = buildTree(inorder, inIndex + 1, inEnd, postorder, postStart + inLeft, postEnd - 1);
        return root;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null) return null;
        //把中序放到hashmap，便于查找
        for (int i = 0; i < inorder.length; i++) {
            hashMap.put(inorder[i], i);
        }
        return buildTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
}

五、 105. 从前序与中序遍历序列构造二叉树

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private HashMap<Integer, Integer> hashMap;
    private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart >= preEnd || inStart >= inEnd) return null;
        int val = preorder[preStart];
        int inIndex = hashMap.get(val);
        int leftIn = inIndex - inStart;
        TreeNode treeNode = new TreeNode(val);
        treeNode.left = buildTree(preorder, preStart + 1, preStart + leftIn + 1, inorder, inStart, inIndex);
        treeNode.right = buildTree(preorder, preStart + leftIn + 1, preEnd, inorder, inIndex + 1, inEnd);
        return treeNode;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) return null;
        hashMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            hashMap.put(inorder[i], i);
        }
        return buildTree(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }
}