二叉树
94. 二叉树的中序遍历
树的遍历分为两种【递归方式】以及【层序遍历】，
如下两种方式均为【递归方式】
方法一：递归遍历
按照左-根-右的顺序进行遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
private void inorder(TreeNode node, List<Integer> res) {
if(node == null) {
return;
}
inorder(node.left, res);
res.add(node.val);
inorder(node.right, res);
}
}
方法二：迭代遍历
利用栈来实现
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while(node != null || !stack.isEmpty()) {
// 节点不为空，入栈，并遍历左子树
if(node != null) {
stack.push(node);
node = node.left;
} else {
// 节点为空，遍历到了叶节点的null；栈不为空，当前null的父节点
node = stack.pop();
// 节点出栈时，构造res
res.add(node.val);
node = node.right;
}
}
return res;
}
}
104. 二叉树的最大深度
方法一：层序遍历
逐层遍历二叉树，在遍历的同时记录树高
class Solution {
public int maxDepth(TreeNode root) {
int res = 0;
// 用于处理 root=[] 的情况
if(root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int len = queue.size();
while(len > 0) {
TreeNode node = queue.poll();
len--;
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
res++;
}
return res;
}
}
小总结：
根据前述两题，树的遍历分为【递归】、【迭代】以及【层序】遍历三种
【递归遍历】：树的三种遍历规则，依次选择 前序、中序、后序 等规则进行（自己调用自己）
【迭代遍历】：类似于树的遍历模拟，采用Stack完成；
- 何时入栈？访问节点就入栈；
- 何时出栈？访问到叶节点，且叶节点为null时才出栈
【层序遍历】：最直观的一种实现方式，使用Queue实现；
- 从左到右依次遍历每一层元素，Queue中元素长度用len记录
- 何时入队？节点不为空，访问节点将其左右孩子入队；
- 何时出队？队中元素个数len>0时，每访问一次Queue则取出一个元素
方法二：递归遍历
重复执行当前代码，取左子树和右子树的最大数高即可，每递归一次树高+1
后序遍历？
class Solution {
public int maxDepth(TreeNode root) {
int res = 0;
if(root == null) {
return res;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
226. 翻转二叉树
方法一：层序遍历 + 交换左右节点
BFS迭代遍历，层序遍历使用队列来实现，在node的左右孩子入队之前，反转左右孩子节点
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int len = queue.size();
while(len > 0) {
TreeNode node = queue.poll();
len--;
// // 反转左右节点
reverse(node);
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
}
return root;
}
private void reverse(TreeNode node) {
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
}
方法二：迭代遍历
DFS前序遍历，使用Stack完成，代码与上述方法实现逻辑较为相近。由于stack是先进后出，而queue是先进先出，因此处理时先让右孩子入栈，再让左孩子入栈
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
reverse(node);
if(node.right != null) stack.push(node.right);
if(node.left != null) stack.push(node.left);
}
return root;
}
private void reverse(TreeNode node) {
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
}
101. 对称二叉树
方法一：层序遍历
利用双端队列，在队列的两端分别进行如对和出队操作，并且比较出对元素的值是否相等
注意：当遍历到的节点为叶节点时，应该continue此次的节点入队操作，阻止叶结点的左右孩子入队
class Solution {
public boolean isSymmetric(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root.left);
deque.offerLast(root.right);
while(!deque.isEmpty()) {
TreeNode leftNode = deque.pollFirst();
TreeNode rightNode = deque.pollLast();
// 左右节点均为空，表明遍历到了叶节点，不加这句，则返回false
if(leftNode == null && rightNode == null) {
continue;
}
if(leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
return false;
}
// 注意此处，节点进入队列的顺序
deque.offerFirst(leftNode.left);
deque.offerFirst(leftNode.right);
deque.offerLast(rightNode.right);
deque.offerLast(rightNode.left);
}
return true;
}
}
543. 二叉树的直径
方法一：递归
假设当前节点为node，那么其左子树node.left的深度为L,，右子树node.right的深度为R，则最大路径距离为L+R+1。
按照上述求解思路，在计算时，仅需要计算左子树的深度L和右子树的深度R，最大深度为Math.max(ans, L+R+1)，最后根节点长度则为ans-1，ans为节点数，因此根节点在计算路径时，被计算了两遍。
class Solution {
int ans;
public int diameterOfBinaryTree(TreeNode root) {
ans = 1;
depth(root);
return ans - 1;
}
// 计算树的深度
private int depth(TreeNode node) {
if(node == null) {
return 0;
}
int L = depth(node.left);
int R = depth(node.right);
ans = Math.max(ans, L+R+1);
return Math.max(L, R) + 1; // 返回值为，以node为根的子树深度
}
}
102. 二叉树的层序遍历
方法一：BFS(层序遍历)
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
List<Integer> list = new ArrayList<>();
// 使用 len 记录，这一层的节点个数
int len = queue.size();
// 层次遍历
while(len > 0) {
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
// 取出一个元素后，将长度减1
len--;
}
res.add(list);
}
return res;
}
}
108. 将有序数组转换为二叉搜索树
方法一：递归，分治法
递归 + 左闭右闭区间，以nums数组中的中间节点mid为root节点，分别对mid左边和右边元素构建左右子树，递归的构建树结构
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length == 0) {
return null;
}
TreeNode root = buildTree(nums, 0, nums.length-1);
return root;
}
private TreeNode buildTree(int[] nums, int left, int right) {
// 当左指针移动到右指针的右边时，该循环就可以停止了
if(left > right) {
return null;
}
// mid 中间值向下（左）取整，左闭右闭区间
int mid = (left + right) >> 1;
// 以当前mid节点为root，分别构建左右子树
TreeNode root = new TreeNode(nums[mid]);
root.left = buildTree(nums, left, mid-1);
root.right = buildTree(nums, mid+1, right);
return root;
}
}
98. 验证二叉搜索树
方法一：递归
通过中序遍历来验证给定的二叉树是否为二叉搜索树。在中序遍历的过程中，节点的值应该按严格递增的顺序排列，如果发现当前节点值不大于前一个节点值，则该树不是有效的二叉搜索树。
解题思路：
- 中序遍历：我们使用中序遍历的特点来验证二叉搜索树。中序遍历二叉搜索树时，节点的值应按严格递增的顺序排列。
- 递归检查：递归地检查左子树和右子树是否满足二叉搜索树的条件。每次遍历到一个节点时，比较它的值是否大于之前遍历到的节点（即
node的值）。如果不满足条件，则直接返回false。 - 边界条件：如果树为空（即
root == null），直接返回true，因为空树也是有效的二叉搜索树。
class Solution {
TreeNode node; // 用于记录当前遍历到的节点的前一个节点
public boolean isValidBST(TreeNode root) {
if(root == null) {
return true; // 空树是有效的二叉搜索树
}
// 递归判断左子树是否为有效的二叉搜索树
boolean left = isValidBST(root.left);
if(!left) return false; // 如果左子树不是有效的BST，则整个树也不是
// 判断当前节点值是否大于前一个节点的值【中序遍历】
if(node != null && root.val <= node.val) {
return false; // 当前节点值小于或等于前一个节点值，则不是有效的BST
}
node = root; // 更新前一个节点为当前节点
// 递归判断右子树是否为有效的二叉搜索树
boolean right = isValidBST(root.right);
return right; // 最终结果由右子树是否为BST决定
}
}
230. 二叉搜索树中第 K 小的元素
方法一：迭代（DFS）
中序遍历（左根右）的排列顺序，即为元素的升序排列顺序，按照该特性选择第K小元素；
class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while(root!= null || !stack.isEmpty()) {
// 中序遍历先遍历左子树，因此需要使用while循环，走到左子树的最左节点
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop(); // 当前弹出元素为root，弹出元素的顺序即为元素的升序排列顺序
k--;
if(k == 0) {
break;
}
root = root.right;
}
return root.val;
}
}
199. 二叉树的右视图
方法一：层序遍历
查看当前子树的右视图，利用BFS层序遍历，当前遍历到每一层的最后一个元素时，该元素为最右元素，将结果记录下来
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int len = queue.size();
while(len > 0) {
TreeNode cur = queue.poll();
// 遍历到最后一个元素时，才记录下该元素（该元素是最右元素）
if(len == 1) {
res.add(cur.val);
}
len--;
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
}
}
return res;
}
}
114. 二叉树展开为链表
方法一：递归，前序遍历
先将前序遍历结果存到list中，之后再利用list中的结果构建单链表
class Solution {
public void flatten(TreeNode root) {
// 先将前序遍历结果存到list中
List<TreeNode> list = new ArrayList<>();
preOrderTraversal(root, list);
// 之后再利用list中的结果构建单链表
int size = list.size();
for(int i=1; i<size; i++) {
TreeNode prev = list.get(i-1), cur = list.get(i);
prev.left = null;
prev.right = cur;
}
}
private void preOrderTraversal(TreeNode root, List<TreeNode> list) {
if(root != null) {
list.add(root);
preOrderTraversal(root.left, list);
preOrderTraversal(root.right, list);
}
}
}
105. 从前序与中序遍历序列构造二叉树
方法一：哈希表 + 递归
class Solution {
Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for(int i=0; i<inorder.length; i++){
map.put(inorder[i], i);
}
return findNode(inorder, 0, inorder.length, preorder, 0, preorder.length);
}
public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] preorder, int preBegin, int preEnd){
if(inBegin >= inEnd || preBegin >= preEnd){
return null;
}
// 前序遍历的第一个位置 --》 根节点
// 记录下当前根节点在中序遍历的位置
int inorderIndex = map.get(preorder[preBegin]);
TreeNode node = new TreeNode(inorder[inorderIndex]);
int distance = inorderIndex - inBegin;
// 左闭右开
node.left = findNode(inorder, inBegin, inorderIndex, preorder, preBegin+1 ,preBegin+1+distance);
node.right = findNode(inorder, inorderIndex+1 ,inEnd, preorder, preBegin+1+distance, preEnd);
return node;
}
}
437. 路径总和 III
方法一：递归
pathSum(root, targetSum)：以当前节点为根，计算从左右子树开始的所有可能的路径，然后递归到左右子节点，继续计算从那里的路径。
**rootSum(root, targetSum) **：从当前节点开始，递归向左右子树搜索路径，每经过一个节点，减去当前节点的值。如果在某个节点发现路径和等于 targetSum，则记录这一条路径。
树遍历的递归过程：根-左-右
- 先以根
root为节点，遍历是否有存在的路径rootSum() - 再遍历
root的左右子树中是否存在路径pathSum()，遍历整个左右子树，包括左子树的左右子树和右子树的左右子树
class Solution {
public int pathSum(TreeNode root, long targetSum) {
if(root == null) {
return 0;
}
int ret = rootSum(root, targetSum);
// 递归调用 pathSum ，计算以左右子树为新的根节点的路径（不包含当前的根节点）
ret += pathSum(root.left, targetSum);
ret += pathSum(root.right, targetSum);
return ret;
}
public int rootSum(TreeNode root, long targetSum) {
int ret = 0;
if(root == null) {
return 0;
}
// 如果当前的 val 为 targetSum，则可行路径长度+1
int val = root.val;
if(val == targetSum) {
ret++;
}
// 递归调用 rootSum()，计算以左右子树为根节点的路径（包含当前的根节点）
ret += rootSum(root.left, targetSum-val);
ret += rootSum(root.right, targetSum-val);
return ret;
}
}
236. 二叉树的最近公共祖先
方法一：递归
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 1. 先看根节点是不是祖先
if(root == null || root == p || root == q) {
return root;
}
// 2. 如果根节点是祖先，有没有更近的祖先呢
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 3. 如果有的话显然只会在一侧 判断一下
if(left == null) {
return right;
}
if(right == null) {
return left;
}
// 4. 如果没有更近的，默认还是返回root
return root;
}
}
.
124. 二叉树中的最大路径和
方法一：递归
maxGain(TreeNode node)是一个递归函数，目的是计算从当前节点 node 开始的最大路径和，同时更新全局最大路径和 ans。
- 递归逻辑：
- 如果当前节点为空（
null），返回 0，表示没有路径。 - 否则，递归计算左子树和右子树的最大路径和，即
maxL和maxR。若某一侧子树的路径和为负值，则忽略它，直接取 0。 - 更新全局最大路径和
ans，计算跨越当前节点、通过左右子树的最大路径（maxL + maxR + node.val）。 - 递归返回值：
maxGain()的返回值是从当前节点向上延伸的最大路径和，但不包括左右子树同时跨越的情况，因为向上递归时路径只能在左或右子树中选择一个方向继续延伸。
- 如果当前节点为空（
ans的更新：ans记录的是全局范围内的最大路径和。在每个节点处，都可能存在一条跨越左右子树的路径，如果这条路径的和比当前的ans大，就更新ans
class Solution {
// 设置全局变量，记录最大路径和
int ans = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return ans;
}
// 计算以node为根节点的树的路径最大值
private int maxGain(TreeNode node) {
// 当前节点为null，则该节点的路径值为0
if(node == null) {
return 0;
}
// node.left的最大值，node.right的最大值，只有结果为正数时才进行更新
int maxL = Math.max(maxGain(node.left), 0);
int maxR = Math.max(maxGain(node.right), 0);
// ans为最大路径和，可以跨越根节点，即从最左节点-根节点-最右
ans = Math.max(ans, maxL + maxR + node.val);
// 返回：以node为根节点的子树（包含node节点）路径最大值
return Math.max(maxL, maxR) + node.val;
}
}