513. 找树左下角的值
注意：左下角的意思是最后一层最左边的节点，不一定是左孩子。
递归法。因为要找深度最深的节点，所以要记录节点的深度
class Solution {
// 最大深度
private int maxDepth = Integer.MIN_VALUE;
// 结果
private int result;
public int findBottomLeftValue(TreeNode root) {
helper(root, 1);
return result;
}
public void helper(TreeNode node, int depth) {
// 叶子节点
// 这里的处理无关遍历顺序，因为是在找最深的叶子节点
if (node.left == null && node.right == null) {
// 找深度最深的节点（即最后一层）
// 因为是前中后序遍历，左节点的遍历一定在右节点之前
// 所以即便最后一层有左右两个子节点，也一定是左节点执行这个判断，更新 maxDepth、result
// 右节点排不上号，这就保证了找到最后一层最靠左的节点
if (depth > maxDepth) {
maxDepth = depth;
result = node.val;
}
}
if (node.left != null) {
depth++;
helper(node.left, depth);
depth--;
}
if (node.right != null) {
depth++;
helper(node.right, depth);
depth--;
}
}
}112. 路经总和
本题的本质是进行深度优先搜索，找到满足条件的路径。使用减法做匹配，每次深入时都减去当前节点的值，直到查找到叶子节点，看查找值和叶子节点是否相等。
// 递归法
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
// 到达叶子节点，如果叶子节点的值正好是要找的值，则表示找到答案
if (root.left == null && root.right == null) return root.val == targetSum;
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;
}
}// 迭代法
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
// 使用栈模拟递归，值为节点和目标值的 pair
Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
stack.push(new Pair<>(root, targetSum));
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> p = stack.pop();
TreeNode node = p.getKey();
int sum = p.getValue();
// 重点，只有是叶子节点，且 node.val == 目标值的才是结果，然后直接返回
if (node.left == null && node.right == null && node.val == sum) return true;
if (node.right != null) {
stack.push(new Pair<>(node.right, sum - node.val));
}
if (node.left != null) {
stack.push(new Pair<>(node.left, sum - node.val));
}
}
return false;
}
}113. 路径总和 II
因为要记录所有符合的路径，所以需要存储结果，并且每次深入时需要记录访问过的路径。
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new LinkedList<>();
if (root != null) {
traversal(root, new LinkedList<>(), targetSum, res);
}
return res;
}
public void traversal(TreeNode node, Deque<Integer> path, int target, List<List<Integer>> res) {
// 访问当前节点，放入 path
path.offerLast(node.val);
// 到达路径终点，即叶子节点，产生解的地方
if (node.left == null && node.right == null && node.val == target) {
res.add((List<Integer>) new LinkedList<>(path));
// res.add((List<Integer>) path);
}
if (node.left != null) {
// target 的深入与回溯
traversal(node.left, path, target - node.val, res);
}
if (node.right != null) {
traversal(node.right, path, target - node.val, res);
}
// 访问结束，退出 path（回溯）
path.pollLast();
}
}106. 从中序与后序遍历序列构造二叉树
先根据后序遍历找到 root，然后根据 root 去中序遍历中划分左右子树的中序遍历，根据左子树中序序列的长度（左子树的中后序长度是相同的），也能去后序遍历中划分左右子树的后序遍历，然后分治，递归处理。
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length == 0 || postorder.length == 0) return null;
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
if (postorder.length == 1) return root;
int idx = -1;
for (int i = 0; i < inorder.length; i++) {
if (postorder[postorder.length - 1] == inorder[i]) {
idx = i;
break;
}
}
// 分割左右子树的中序和后续数组
int[] leftInorder = Arrays.copyOfRange(inorder, 0, idx);
int[] leftPostorder = Arrays.copyOfRange(postorder, 0, leftInorder.length);
int[] rightInorder = Arrays.copyOfRange(inorder, idx + 1, inorder.length);
int[] rightPostorder = Arrays.copyOfRange(postorder, leftPostorder.length, postorder.length - 1);
root.left = buildTree(leftInorder, leftPostorder);
root.right = buildTree(rightInorder, rightPostorder);
return root;
}
}105. 从前序与中序遍历序列构造二叉树
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) return null;
TreeNode root = new TreeNode(preorder[0]);
if (preorder.length == 1) return root;
int idx = -1;
for (int i = 0; i < inorder.length; i++) {
if (preorder[0] == inorder[i]) {
idx = i;
break;
}
}
int[] leftInorder = Arrays.copyOfRange(inorder, 0, idx);
int[] leftPreorder = Arrays.copyOfRange(preorder, 1, leftInorder.length + 1);
int[] rightInorder = Arrays.copyOfRange(inorder, idx + 1, inorder.length);
int[] rightPreorder = Arrays.copyOfRange(preorder, leftPreorder.length + 1, preorder.length);
root.left = buildTree(leftPreorder, leftInorder);
root.right = buildTree(rightPreorder, rightInorder);
return root;
}
}