文章目录
一、找树左下角的值
参考链接513. 找树左下角的值 - 力扣（LeetCode）
二叉树的最深最左侧的节点的值，涉及到最深 -> 联想到 层序遍历
BFS
class Solution {
public int findBottomLeftValue(TreeNode root) {
Deque<TreeNode> d = new ArrayDeque<>();
d.addLast(root);
int ans = 0;
while (!d.isEmpty()) {
int sz = d.size();
ans = d.peek().val;
while (sz-- > 0) {
TreeNode poll = d.pollFirst();
if (poll.left != null) d.addLast(poll.left);
if (poll.right != null) d.addLast(poll.right);
}
}
return ans;
}
}
DFS
class Solution {
int max, ans;
public int findBottomLeftValue(TreeNode root) {
dfs(root, 1);
return ans;
}
void dfs(TreeNode root, int depth) {
if (root == null) return ;
if (depth > max) {
max = depth; ans = root.val;
}
//左侧先执行dfs方法，如果最后一行存在多个节点，那么左侧的节点必定先执行
//那么当执行到右侧的时候由于 depth == max，最先记录的永远是最左边的节点
dfs(root.left, depth + 1);
dfs(root.right, depth + 1);
}
}
二、路径总和1 & 2
从路径总和1 & 2体会什么情况下递归需要返回值，什么时候不需要返回值
路径总和1
初始递归
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
// 如果根节点为空，直接返回false
if (root == null) return false;
// 如果当前节点是叶子节点（即左右子节点都为空），检查路径和是否等于目标值
if (root.left == null && root.right == null) {
return sum == root.val;
}
// 如果当前节点不是叶子节点，递归地在左子树和右子树中查找路径
// 路径和等于目标值减去当前节点的值
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
DFS
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
// 如果根节点为空，直接返回false
if (root == null) return false;
// 调用深度优先搜索（DFS）函数，查找是否存在一条从根节点到叶子节点的路径，使得路径上的节点值之和等于给定的目标值
return dfs(root, sum, root.val);
}
private boolean dfs(TreeNode root, int target, int pathSum) {
// 如果当前节点为空，直接返回false
if (root == null) return false;
// 如果路径和等于目标值，并且当前节点是叶子节点（即左右子节点都为空），返回true
if (pathSum == target && root.left == null && root.right == null) {
return true;
}
// 初始化左右子树的标志位为false
boolean leftFlag = false, rightFlag = false;
// 如果左子节点不为空，递归地在左子树中查找路径，路径和等于当前路径和加上左子节点的值
if (root.left != null) {
leftFlag = dfs(root.left, target, pathSum + root.left.val);
}
// 如果右子节点不为空，递归地在右子树中查找路径，路径和等于当前路径和加上右子节点的值
if (root.right != null) {
rightFlag = dfs(root.right, target, pathSum + root.right.val);
}
// 如果左子树或右子树中存在满足条件的路径，返回true，否则返回false
return leftFlag || rightFlag;
}
BFS
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
// 如果根节点为空，直接返回false
if (root == null) return false;
// 创建一个队列，用于广度优先搜索（BFS）
Deque<Pair<TreeNode, Integer>> queue = new LinkedList<>();
// 将根节点和它的值作为一个对（Pair）添加到队列中
queue.offer(new Pair<>(root, root.val));
// 当队列不为空时，继续循环
while (!queue.isEmpty()) {
// 从队列中取出一个对
Pair<TreeNode, Integer> pair = queue.poll();
// 获取对中的节点和路径和
TreeNode node = pair.getKey();
int pathSum = pair.getValue();
// 如果当前节点是叶子节点（即左右子节点都为空），并且路径和等于目标值，返回true
if (node.left == null && node.right == null && pathSum == sum) {
return true;
}
// 如果左子节点不为空，将左子节点和当前路径和加上左子节点的值作为一个对添加到队列中
if (node.left != null) {
queue.offer(new Pair<>(node.left, pathSum + node.left.val));
}
// 如果右子节点不为空，将右子节点和当前路径和加上右子节点的值作为一个对添加到队列中
if (node.right != null) {
queue.offer(new Pair<>(node.right, pathSum + node.right.val));
}
}
// 如果遍历完所有节点都没有找到满足条件的路径，返回false
return false;
}
路径总和2
参考链接113. 路径总和 II - 力扣（LeetCode）
先序遍历 + 路径记录
class Solution {
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
recur(root, targetSum);
return res;
}
void recur(TreeNode root, int tar) {
if (root == null) return;
path.add(root.val);
tar -= root.val;
if (tar == 0 && root.left == null && root.right == null)
res.add(new LinkedList<Integer>(path));
recur(root.left, tar);
recur(root.right, tar);
path.removeLast();
}
}
三、从中序与后序遍历序列构造二叉树
class Solution {
Map<Integer, Integer> map; // 方便根据数值查找位置
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
map.put(inorder[i], i);
}
return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开
}
public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
// 参数里的范围都是前闭后开
if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开，说明没有元素，返回空树
return null;
}
int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置
TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数
root.left = findNode(inorder, inBegin, rootIndex,
postorder, postBegin, postBegin + lenOfLeft);
root.right = findNode(inorder, rootIndex + 1, inEnd,
postorder, postBegin + lenOfLeft, postEnd - 1);
return root;
}
}
四、从前序和中序遍历序列构造二叉树
注，本文方法只适用于“无重复节点值”的二叉树。
为了提升效率，本文使用哈希表 dic 存储中序遍历的值与索引的映射，查找操作的时间复杂度为 O(1) 。
class Solution {
int[] preorder;
HashMap<Integer, Integer> dic = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for(int i = 0; i < inorder.length; i++)
dic.put(inorder[i], i);
return recur(0, 0, inorder.length - 1);
}
TreeNode recur(int root, int left, int right) {
if (left > right) return null; // 递归终止
TreeNode node = new TreeNode(preorder[root]); // 建立根节点
int i = dic.get(preorder[root]); // 划分根节点、左子树、右子树
node.left = recur(root + 1, left, i - 1); // 开启左子树递归
node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
return node; // 回溯返回根节点
}
}