二叉树刷题（JAVA）

引入：

递归是一种在函数定义中使用函数自身的方法。它是一种常见的编程技巧，用于解决可以被分解为相同问题的子问题的问题。

递归函数通常包含两个部分：基本情况和递归情况。

基本情况是指递归函数停止调用自身的条件。当满足基本情况时，递归函数将不再调用自身，而是返回一个特定的值或执行特定的操作。

递归情况是指递归函数调用自身解决更小规模的子问题。通过不断地调用自身，递归函数可以将原始问题分解为更小的子问题，直到达到基本情况。

让我们再看二叉树的遍历，其实它的结构大概是这样(基本框架)：

public void traverse(TreeNode root) {
        //前序遍历的位置
        traverse(root.left);
        //中序遍历的位置
        traverse(root.right);
        //后续遍历的位置
    }

例1：二叉树的前序遍历：

题目:给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

输入：root = [1,null,2,3]
输出：[1,2,3]

题目链接：144. 二叉树的前序遍历 - 力扣（LeetCode）

import java.util.LinkedList;
import java.util.List;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;}
}

前序遍历

public class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>(); // 在这里初始化列表if (root == null) {return list; // 如果根节点为空，返回空列表}// 直接进行递归调用list.add(root.val); // 访问当前节点list.addAll(preorderTraversal(root.left)); // 遍历左子树list.addAll(preorderTraversal(root.right)); // 遍历右子树return list; // 返回结果列表}
}

中序遍历

public class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>(); // 在这里初始化列表if (root == null) {return list; // 如果根节点为空，返回空列表}// 直接进行递归调用list.addAll(preorderTraversal(root.left)); // 遍历左子树list.add(root.val); // 访问当前节点list.addAll(preorderTraversal(root.right)); // 遍历右子树return list; // 返回结果列表}
}

后序遍历

public class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>(); // 在这里初始化列表if (root == null) {return list; // 如果根节点为空，返回空列表}// 直接进行递归调用list.addAll(preorderTraversal(root.left)); // 遍历左子树list.addAll(preorderTraversal(root.right)); // 遍历右子树list.add(root.val); // 访问当前节点return list; // 返回结果列表}
}

例2：N叉树的前序遍历

注：由于N叉树（不止包含左右子节点，可能有多个）的特性，其没有中序遍历，其大致框架是：

class Solution{
public void traverse(TreeNode root){
List<Ingeter> list=new LinkedList<>();
if(root==null){
return list;
}
list.add(root);
traverse(root.left);
traverse(root.right);return list;
}
}

  public void traverse(TreeNode root){if(root == null){return ;}//前序遍历的位置for(Node child : root.children){traverse(child);}//后序遍历的位置}

题目：

给定一个 n 叉树的根节点  root ，返回 其节点值的 前序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

题目链接：589. N 叉树的前序遍历 - 力扣（LeetCode）

题解：

class Solution {public List<Integer> preorder(Node root) {List<Integer> list=new LinkedList<>();prehelp(root,list);return list;}public void prehelp(Node root,List<Integer> list){if(root==null){return ;}list.add(root.val);//这一步添加了列表元素for(Node n:root.children){prehelp(n,list);}}    
}class Solution {public List<Integer> preorder(Node root) {List<Integer> list=new LinkedList<>();prehelp(root,list);return list;}public void prehelp(Node root,List<Integer> list){if(root==null){return ;}list.add(root.val);//这一步添加了列表元素for(Node n:root.children){prehelp(n,list);}}    
}

关于最大最小使用三目操作符与Math.max()操作符的建议：

• 当 leftHeight 和 rightHeight 不相等时，条件运算符可能导致返回不准确的深度（例如如果 leftHeight 更大而你错误地选择了它），因此在不同情况下可能会出现问题。
• Math.min 则始终保证选择最小的深度。

虽然在特定情况下（如 leftHeight 和 rightHeight 相等时）两种方法返回相同的结果，但 Math.min 方法更安全、可读性更好。因此，在实际编程中，推荐使用 Math.min 来确保准确性和代码的清晰度。

例3：二叉树的最大深度：

题目：

给定一个二叉树 root ，返回其最大深度。 

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

输入：root = [3,9,20,null,null,15,7]
输出：3

题目链接：104. 二叉树的最大深度 - 力扣（LeetCode）

法一：通过二叉树的遍历将其转化为左右子树的最大深度+1（自身）的方式进行求解：

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return (leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);}}
}

例4：二叉树的最小深度 

题目：

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。

题目链接：111. 二叉树的最小深度 - 力扣（LeetCode））

题解：

法一：分解问题，不断求左右子树最小值：

class Solution {public int minDepth(TreeNode root) {if (root == null) {return 0;} else if(root.left==null&&root.right!=null){return minDepth(root.right)+1;}else if(root.right==null&&root.left!=null){return minDepth(root.left)+1;}else {int leftHeight = minDepth(root.left);int rightHeight = minDepth(root.right);return Math.min(leftHeight, rightHeight) + 1;}}
}

错误原因：

没有考虑到，若左右子树有一树为空，那么有一颗树的返回值就是0

而最后用Math.min获取了元素的最小值，就会返回0+1

法二：迭代思想：与最小深度类似，但这里需要多一个判断是否是叶子节点，是叶子节点是我们才刷新最小值，不然开始就是最小值后续不会在改变，小细节，开始就定义一个极大值，为后续的找最小值做准备

class Solution {int depth = 0;int res = Integer.MAX_VALUE;public  void traverse(TreeNode root){if(root == null){return ;}depth++;if(root.left == null && root.right == null){res = Math.min(res,depth);}traverse(root.left);traverse(root.right);depth--;}public int minDepth(TreeNode root) {if(root == null){return 0;}traverse(root);return res;}}

例5：N叉树的最大深度：

题目：

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

题目链接

559. N 叉树的最大深度 - 力扣（LeetCode）

题解：与二叉树的最大深度基本一致，就是要遍历所有子树：

class Solution {public int maxDepth(Node root) {if(root==null){return 0;}int maxChildDepth=0;for(Node n:root.children){int childDepth=maxDepth(n);maxChildDepth=Math.max(childDepth,maxChildDepth);}return maxChildDepth+1;}
}

主要没想到怎么获取每个子树的最大值

可通过将每次获取到的最大值让max这个数保存起来，后用Math.max()获取最大值，这样获取最大深度

例6：左叶子之和：

题目：给定二叉树的根节点 root ，返回所有左叶子之和。

题目链接：404. 左叶子之和 - 力扣（LeetCode）

题解：通过给函数传一个boolean值通过二叉树的遍历来判断是否是左叶子节点。然后将是左叶子节点的值相加

class Solution {public int sumOfLeftLeaves(TreeNode root) {return root != null ? dfs(root) : 0;}public int dfs(TreeNode node) {int ans = 0;if (node.left != null) {ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);}if (node.right != null && !isLeafNode(node.right)) {ans += dfs(node.right);}return ans;}public boolean isLeafNode(TreeNode node) {return node.left == null && node.right == null;}
}

为什么没有像到：

想的太碎了，将点分为了多个：如左子节点为空，右子节点不为空

左子节点不为空，右子节点为空

左右子节点都不为空

左右子节点都为空

思路总结：

1.单独抽象一个方法，判断是否为叶子节点

2.递归调用，判断每一个左子节点：左子树（左子节点）不为空

                                                          是叶子节点，累加，不是 继续调用函数

                                                          右子树不为空，且不是叶子节点

                                                          调用函数

例7：翻转二叉树：

题目：

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

题目链接：226. 翻转二叉树 - 力扣（LeetCode）

题解：在前序遍历的基础上交换左右子树即可（图解）：

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null){return null;}//交换左右子树TreeNode temp = root.left;root.left = root.right;root.right = temp;invertTree(root.left);invertTree(root.right);return root;}
}

为什么没有想到：

1.想到了对称二叉树

2.将

1. TreeNode temp = root.left;

2. root.left = root.right;

3. root.right = temp;

这段代码理解成了节点互换，并没有互换左右子树

例8: 路径总和：

题目：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

题目链接：112. 路径总和 - 力扣（LeetCode）

题解：法一：在前序遍历位置记录路径的和（节点的val值累加），后序遍历的位置删除路径的和（节点的val值减少）：

采用递归

class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) {return false; // 基础条件：如果节点为空，返回 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); // 递归检查左子树和右子树}
}

段代码实现了一个名为 hasPathSum 的方法，用于判断一棵二叉树是否存在从根节点到某个叶子节点的路径，其路径上所有节点值的和等于给定的目标值 sum。

例9：路径总和II:

题目：

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

题目链接：113. 路径总和 II - 力扣（LeetCode）

题解：遍历一遍二叉树，就可以把所有符合条件的路径找出来。为了维护经过的路径，在进入递归的时候要在 path 列表添加节点，结束递归的时候删除节点。

class Solution {List<List<Integer>> res = new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int sum) {if (root == null) return res;traverse(root, sum, new LinkedList<>());return res;}// 遍历二叉树private void traverse(TreeNode root, int sum, LinkedList<Integer> path) {if (root == null) return;int remain = sum - root.val;if (root.left == null && root.right == null) {if (remain == 0) {// 找到一条路径path.addLast(root.val);res.add(new LinkedList<>(path));path.removeLast();}return;}// 维护路径列表path.addLast(root.val);traverse(root.left, remain, path);path.removeLast();path.addLast(root.val);traverse(root.right, remain, path);path.removeLast();}
}

例10：二叉树展开为链表：

题目：

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

题目链接：114. 二叉树展开为链表 - 力扣（LeetCode）

题解：只要运用二叉树的递归遍历框架即可；后者的关键在于明确递归函数的定义，然后利用这个定义，这题就属于后者，flatten 函数的定义如下：给 flatten 函数输入一个节点 root，那么以 root 为根的二叉树就会被拉平为一条链表。流程：

1、将 root 的左子树和右子树拉平。

2、将 root 的右子树接到左子树下方，然后将整个左子树作为右子树。

class Solution {// 定义：将以 root 为根的树拉平为链表public void flatten(TreeNode root) {// base caseif (root == null) return;// 先递归拉平左右子树flatten(root.left);flatten(root.right);/****后序遍历位置****/// 1、左右子树已经被拉平成一条链表TreeNode left = root.left;TreeNode right = root.right;// 2、将左子树作为右子树root.left = null;root.right = left;// 3、将原先的右子树接到当前右子树的末端TreeNode p = root;while (p.right != null) {p = p.right;}p.right = right;}
}

  到这里，竹竹零就要和大家说再见了🍕🍕🍕

如果您觉得有失偏颇请您在评论区指正，如果您觉得不错的话留个好评再走吧！！

您的鼓励就是对我最大的支持!  ！ ！