算法

【新手007】二叉树更多题

Posted by Hilda on September 10, 2025

1.力扣102二叉树按层遍历并收集节点

力扣：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/

同题目，但是返回要求不太一样的牛客：（填函数风格）https://www.nowcoder.com/practice/d8566e765c8142b78438c133822b5118

1.1层序遍历

首先先要学会二叉树的层序遍历：即力扣102. 二叉树的层序遍历，：https://leetcode.cn/problems/binary-tree-level-order-traversal/

牛客（填函数风格）：https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3

image-20250907212315011

思路是：

  • 准备一个队列，维持一个变量size，进入节点多少个就维持size=几
  • 加入节点的孩子，先左再右
  • 弹出size个节点，弹出一个节点就加入其孩子（先左再右）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

/**
 * 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>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> curAns = new ArrayList<>();
            for (int i = 0;i < size;i++) {
                TreeNode cur = queue.poll();
                curAns.add(cur.val);
                if (cur.left != null) {
                    queue.add(cur.left);
                } 
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
            ans.add(curAns);
        }
        return ans;
    }
}

【特别注意】：size一定要提前获取，因为queue在for循环中有动态增加的过程。

1.2逆序的层序遍历

如何得到逆序的程序遍历呢？

  • 方法1:用ArrayList，先收集顺序的，然后逆过来。或者加入位置每次都是0，比如下面的解法也可以换成ArrayList<Integer> curAns = new ArrayList<>();
  • 方法2:用LinkedList，每次头插法。

方法2解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/**
 * 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>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> curAns = new ArrayList<>();
            int size = queue.size();
            for (int i = 0;i < size;i++) {
                TreeNode cur = queue.poll();
                curAns.add(cur.val);
                if(cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
            ans.add(0, curAns);
        }
        return ans;
    }
}

如果用ArrayList也可以：(牛客测试通过了：https://www.nowcoder.com/practice/d8566e765c8142b78438c133822b5118)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrderBottom (TreeNode root) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> curAns = new ArrayList<>();
            for (int i = 0;i < size;i++) {
                TreeNode cur = queue.poll();
                curAns.add(cur.val);
                if(cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
            ans.add(0,curAns);
        }
        return ans;
    }

}

1.3java中的Stack需要注意的点

java中的Stack<Integer> stack = new Stack<>();很坑。java中实现的栈Stack比较慢，可以用LinkedList优化常数时间。LinkedList就是双端队列，需要使用栈的时候，从尾巴入，从尾巴出即可，或者从头入，从头出。

为什么栈Stack很慢？Stack 类继承自 java.util.Vector。Vector 是一个线程安全的动态数组，这意味着它的大部分方法（如 push, pop）都使用了 synchronized 关键字。synchronized 关键字会引入锁的开销，即使在单线程环境下，这种开销也无法避免。这使得 Stack 的性能比非同步的集合类（如 ArrayList 或 LinkedList）要慢。

LinkedList 实现了 java.util.Deque（双端队列）接口。Deque 接口提供了非常清晰和高效的栈操作方法：

  • 入栈（Push）：使用 addFirst() 或 push() 方法将元素添加到列表的头部。
  • 出栈（Pop）：使用 removeFirst() 或 pop() 方法移除并返回列表头部的元素。
  • 查看栈顶元素：使用 peekFirst() 或 peek() 方法查看但不移除头部的元素。

这些操作的都是在链表的头部进行，所以时间复杂度都是 O(1)

虽然 ArrayList 也可以实现栈，但 LinkedList 是更优的选择。

但是，如果光是从sync角度分析 的确是stack性能要差一些 但是stack底层的vector毕竟数据结构是数组 而LinkedList底层数据结构为链表

看要比较哪方面的性能了 因为链表还要维护每个节点的next的引用

但是，如果知道容器要放多少个数，一定是数组最快。

2.判断是否是平衡搜索二叉树

LCR 176. 判断是否为平衡二叉树：https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/

牛客-判断是不是平衡二叉树（填函数风格）：https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222

2.1是否是平衡二叉树

平衡二叉树的定义：当二叉树的任意一棵子树的左子树的高度和右子树的高度相差不超过1时，该二叉树为平衡二叉树。

根据定义可知，要确认一个二叉树是否是平衡二叉树势必要遍历所有结点。而遍历到每个结点时，要想知道以该结点为根结点的子树是否是平衡二叉树，我们要收集两个信息：

  • 该结点的左子树、右子树是否是平衡二叉树
  • 左右子树的高度分别是多少，相差是否超过1

那么我们来到某个结点时（子过程），我们需要向上层（父过程）返回的信息就是该结点为根结点的树是否是平衡二叉树以及该结点的高度，这样的话，父过程就能继续向上层返回应该收集的信息。

递归很好用，该题中的递归用法也是一种经典用法，可以高度套路：

  1. ​ 分析问题的解决需要哪些步骤（这里是遍历每个结点，确认每个结点为根节点的子树是否为平衡二叉树）
  2. ​ 确定递归：父问题是否和子问题相同
  3. ​ 子过程要收集哪些信息
  4. ​ 本次递归如何利用子过程返回的信息得到本过程要返回的信息
  5. ​ base case

代码如下：测试链接：https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/

和https://leetcode.cn/problems/balanced-binary-tree/description/ 两道题一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/**
 * 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 {
    class Info {
        public boolean isBal;
        public int height;
        public Info(boolean b, int h) {
            this.isBal = b;
            this.height = h;
        }
    }
    public boolean isBalanced(TreeNode root) {
        return process(root).isBal;
    }

    public Info process(TreeNode root) {
        if (root == null) {
            return new Info (true, 0);
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        boolean isBal = leftInfo.isBal && rightInfo.isBal && (Math.abs(leftInfo.height - rightInfo.height) < 2);
        return new Info(isBal, height);
    }
    
}

2.2是否是搜索二叉树

搜索二叉树的定义：对于二叉树的任意一棵子树，其左子树上的所有结点的值小于该子树的根节点的值，而其右子树上的所有结点的值大于该子树的根结点的值，并且整棵树上任意两个结点的值不同。

力扣测试链接：https://leetcode.cn/problems/validate-binary-search-tree/description/

牛客填函数风格：https://www.nowcoder.com/practice/a69242b39baf45dea217815c7dedb52b?tpId=295

  • 方法1:根据定义，搜索二叉树的中序遍历打印将是一个升序序列。因此我们可以利用二叉树的中序遍历的非递归方式，比较中序遍历时相邻两个结点的大小，只要有一个结点的值小于其后继结点的那就不是搜索二叉树。
  • 方法2:递归，每个节点维护3个信息：是否是搜索二叉树，整棵树最大值，整棵树最小值。

方法2的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

/**
 * 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 {
    class Info {
        public boolean isBst;
        public int max;
        public int min;
        public Info (boolean is, int ma, int mi) {
            isBst = is;
            max = ma;
            min = mi;
        }
    }
    public boolean isValidBST (TreeNode root) {
        return process(root).isBst;
    }

    public Info process (TreeNode root) {
        if (root == null) {
            return null;
        }

        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);

        int max = root.val;
        int min = root.val;
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
        }
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
        }
        boolean leftIsBst = leftInfo == null ? true : leftInfo.isBst;
        boolean rightIsBst = rightInfo == null ? true : rightInfo.isBst;
        boolean leftLess = leftInfo == null ? true : (leftInfo.max < root.val) ;
        boolean rightBigger = rightInfo == null ? true : (rightInfo.min > root.val);
        boolean isBst  = leftIsBst && rightIsBst && leftLess && rightBigger;
        return new Info(isBst, max, min);

    }
}

2.3是否是平衡搜索二叉树

上面两个结果相互与&即可。

3.能否组成路径和

https://leetcode.cn/problems/path-sum/description/

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

/**
 * 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 static boolean isSum  = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        isSum = false;
        process(root, 0, targetSum);
        return isSum;
    }

    public void process(TreeNode root, int preSum, int sum) {
        if (root.left == null && root.right == null) {
            if (root.val + preSum == sum) {
                isSum = true;
            }
            return;
        }

        preSum += root.val;
        if (root.left != null) {
            process(root.left, preSum, sum);
        }
        if (root.right != null) {
            process(root.right, preSum, sum);
        }
    }
}

4.收集达标路径和

测试链接：https://leetcode.cn/problems/path-sum-ii/description/

当遍历到叶子节点（即 root.left == null && root.right == null）时，检查当前节点的值加上之前路径的和 preSum 是否等于目标值 sum。如果相等，将当前节点值添加到 path 中，然后将 path 的一个副本添加到结果列表 ans 中。为什么需要副本？因为 path 是一个引用，后续的递归调用会对其进行修改，如果不复制，添加到 ans 中的路径会不断变化。最后，从 path 中移除当前节点值，进行回溯（“清理现场”），以便返回到上一层继续遍历其他分支。

如果不是叶子节点，将当前节点的值添加到 path 中，并更新 preSum。如果当前节点的左子节点不为空，递归调用 process(root.left, ...) 继续向左遍历。如果当前节点的右子节点不为空，递归调用 process(root.right, ...) 继续向右遍历。

在左右子树的遍历都完成后，从 path 中移除当前节点的值，进行回溯（也需要清理现场）。这确保了当递归返回到上一层时，路径状态是正确的，不会受到当前节点的影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

/**
 * 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>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        List<Integer> path = new ArrayList<>();
        process(root, path, 0, targetSum, ans);
        return ans;
    }

    public void process(TreeNode root, List<Integer> path, int preSum, int sum, List<List<Integer>> ans ) {
        // 叶节点  base  case
        if (root.left == null && root.right == null) {
            if (root.val + preSum == sum) {
                path.add(root.val);
                ans.add(copy(path));
                path.remove(path.size() - 1);// 清理现场
            }
            return;
        }
        path.add(root.val);
        preSum += root.val;
        if (root.left != null) {
            process(root.left, path, preSum, sum, ans);
        }
        if (root.right != null) {
            process(root.right, path, preSum, sum, ans);
        }
        path.remove(path.size() - 1);// 清理现场
    }

    public List<Integer> copy(List<Integer> l) {
        List<Integer> ans = new ArrayList<>();
        for (int i: l) {
            ans.add(i);
        }
        return ans;
    }
}
CATALOG
    FEATURED TAGS
    书籍阅读 算法 人工智能AI基础 python基础 力扣 numpy pandas 机器学习-吴恩达 机器学习算法 matplotlib spring6 Java基础 java集合 ollama工具 python爬虫
    FRIENDS