一、 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);
}
}
