二叉树刷题（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.将

TreeNode temp = root.left;

root.left = root.right;

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 case
        if (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;
 
 
 
    }
}