面试经典 150 题-二叉树

LeetCode 面试经典 150 题-二叉树

二叉树的最大深度

深度优先搜索

当前节点最大深度为max(左子树最大深度, 右子树最大深度) + 1.

1
2
3
4
5
6
7
8
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。

广度优先搜索

每次拓展下一层的时候，不同于广度优先搜索的每次只从队列里拿出一个节点，我们需要将队列里的所有节点都拿出来进行拓展，这样能保证每次拓展完的时候队列里存放的是当前层的所有节点，即我们是一层一层地进行拓展，最后我们用一个变量 ans 来维护拓展的次数。

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 int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 定义队列
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        // 广度优先搜索
        int ans = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            // 遍历每一层所有结点
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                if (node.left != null) {
                    que.offer(node.left);
                }
                if (node.right != null) {
                    que.offer(node.right);
                }
            }
            ans++;
        }
        return ans;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

相同的树

递归

如果当前结点不相同，则返回false，否则递归判断左子树和右子树是否相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

翻转二叉树

深度优先搜索

  1. 边界处理，为空直接返回；
  2. 递归翻转左右子树；
  3. 翻转当前结点；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        
        // 递归翻转左右子树
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        // 交换当前左右子树
        root.left = right;
        root.right = left;

        return root;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

对称二叉树

深度优先搜索

需要判断左右子树值是否相等，以及左子树的左子树是否等于右子树的右子树，以及左子树的右子树是否等于右子树的左子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 边界处理
        if (root == null) {
            return true;
        }
        
        return helper(root.left, root.right);
    }

    private boolean helper(TreeNode left, TreeNode right) {
        if (left == null || right == null) {
            return left == right;
        }
        return left.val == right.val && helper(left.left, right.right) && helper(left.right, right.left);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

广度优先搜索

使用队列实现，每次弹出两个结点，比较其是否相等，在添加结点时，按照相反的顺序添加。

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
class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        que.offer(root);

        // 广度优先搜索
        while (!que.isEmpty()) {
            TreeNode u = que.poll();
            TreeNode v = que.poll();
            // 如果为空
            if (u == null && v == null) {
                continue;
            }
            if (u == null || v == null || u.val != v.val) {
                return false;
            } 

            // 交错顺序放入队列
            que.offer(u.left);
            que.offer(v.right);
            que.offer(u.right);
            que.offer(v.left);
        }

        return true;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

从前序与中序遍历序列构造二叉树

分析

  1. 将中序遍历序列存入哈希表，方便查找。
  2. 定义递归函数处理：
    1. 递归结束：前序数组遍历完；
    2. O(1)时间在中序遍历中找到根节点；
    3. 递归遍历左右子树；
    4. 连接子树，返回当前节点；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < n; i++) {
            index.put(inorder[i], i);
        }
        return dfs(preorder, index, 0, n, 0, n);
    }

    private TreeNode dfs(int[] preorder, Map<Integer, Integer> index, int preL, int preR, int inL, int inR) {
        // 递归结束
        if (preL == preR) {
            return null;
        }
        // 计算左子树大小
        int leftSize = index.get(preorder[preL]) - inL;
        TreeNode left = dfs(preorder, index, preL + 1, preL+1+leftSize, inL, inL+leftSize);
        TreeNode right = dfs(preorder, index, preL+1+leftSize, preR, inL+1+leftSize, inR);
        // 连接子树
        return new TreeNode(preorder[preL], left, right);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

从中序与后序遍历序列构造二叉树

分析

同上题:

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
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        // 将中序序列存入哈希表
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < n; i++) {
            index.put(inorder[i], i);
        }
        return dfs(postorder, index, 0, n, 0, n);
    }

    private TreeNode dfs(int[] postorder, Map<Integer, Integer> index, int postL, int postR, int inL, int inR) {
        // 递归结束
        if (postL == postR) {
            return null;
        }
        // 计算左右子树
        int leftSize = index.get(postorder[postR-1]) - inL;
        TreeNode left = dfs(postorder, index, postL, postL + leftSize, inL, inL + leftSize);
        TreeNode right = dfs(postorder, index, postL + leftSize, postR - 1, inL + leftSize + 1, inR);

        // 连接子树
        return new TreeNode(postorder[postR-1], left, right);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

填充每个节点的下一个右侧节点指针II

层序遍历

使用队列实现层序遍历。

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
class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        // 定义队列
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        // 广度优先搜索
        while (!que.isEmpty()) {
            int n = que.size();
            Node pre = null;
            for (int i = 0; i < n; i++) {
                Node node = que.poll();
                if (i != 0) {
                    pre.next = node;
                }
                pre = node;
                if (node.left != null) {
                    que.offer(node.left);
                }
                if (node.right != null) {
                    que.offer(node.right);
                }

            }
        }

        return root;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

BFS+链表

  • 从第一层开始（第一层只有一个 root 节点），每次循环：
  • 遍历当前层的链表节点，通过节点的 left 和 right 得到下一层的节点。
  • 把下一层的节点从左到右连接成一个链表。
  • 拿到下一层链表的头节点，进入下一轮循环。
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
class Solution {
    public Node connect(Node root) {
        Node dummy = new Node();
        Node cur = root;
        
        // 广度优先搜索
        while (cur != null) {
            dummy.next = null;
            Node nxt = dummy;   // 下一层链表
            // 遍历当前层链表
            while (cur != null) {
                if (cur.left != null) {
                    nxt.next = cur.left;
                    nxt = cur.left;
                }
                if (cur.right != null) {
                    nxt.next = cur.right;
                    nxt = cur.right;
                }
                cur = cur.next; // 当前层下一个节点
            }
            // 下一层链表
            cur = dummy.next;
        }

        return root;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

二叉树展开为链表

先序遍历-递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> arr = new ArrayList<>();
        preOrder(root, arr);

        // 把先序遍历的结果链接成链表
        for (int i = 1; i < arr.size(); i++) {
            TreeNode pre = arr.get(i - 1);
            TreeNode cur = arr.get(i);
            pre.left = null;
            pre.right = cur;
        }
    }

    private void preOrder(TreeNode root, List<TreeNode> arr) {
        // 按照根、左、右的顺序
        if (root != null) {
            arr.add(root);
            preOrder(root.left, arr);
            preOrder(root.right, arr);
        }
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

先序遍历-迭代

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
class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> arr = new ArrayList<>();
        // 迭代
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                arr.add(node);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }

        // 把先序遍历的结果链接成链表
        for (int i = 1; i < arr.size(); i++) {
            TreeNode pre = arr.get(i - 1);
            TreeNode cur = arr.get(i);
            pre.left = null;
            pre.right = cur;
        }
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

Morris遍历

  1. 将左子树插入到右子树的地方
  2. 将原来的右子树接到左子树的最右边节点
  3. 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public void flatten(TreeNode root) {
        while (root != null) {
            // 左子树为空，考虑下一个节点
            if (root.left == null) {
                root = root.right;
            } else {
                // 找到左子树上最右边的节点
                TreeNode pre = root.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                // 将根节点右子树链到左子树最右边节点的右子树上
                pre.right = root.right;
                // 左子树放到右子树
                root.right = root.left;
                root.left = null;
                // 下一个节点
                root = root.right;
            }
        }
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

后序遍历-递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    private TreeNode pre = null;

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.right);
        flatten(root.left);
        root.right = pre;
        root.left = null;
        pre = root;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

后序遍历-迭代

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
class Solution {
    public void flatten(TreeNode root) {
        Deque<TreeNode> stack  = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode pre = null;

        while (cur != null || !stack.isEmpty()) {
            // 右子树入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.right;
            }
            cur = stack.peek();
            // 在不存在左节点或者右节点已经访问过的情况下，访问根节点
            if (cur.left == null || cur.left == pre) {
                stack.pop();
                cur.right = pre;
                cur.left = null;
                pre = cur;
                cur = null;
            } else {
                // 先访问左子树
                cur = cur.left;
            }
        }
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

路径总和

深度优先搜索

  • 递归结束：当前节点为空，返回false。如果当前节点为叶子结点，则判断当前节点值是否等于target。
  • 递归计算左右子树。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }

        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

广度优先搜索

队列中存储结点和当前路径和的键值对，在广度遍历的过程中判断是否是叶子节点且和满足条件。

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
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        // 队列中存储的是 (当前节点, 当前路径和)
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, root.val));

        while (!queue.isEmpty()) {
            // 获取当前节点和当前路径和
            Pair<TreeNode, Integer> pair = queue.poll();
            TreeNode node = pair.getKey();
            int currentSum = pair.getValue();

            // 判断是否为叶子节点且路径和等于目标值
            if (node.left == null && node.right == null && currentSum == targetSum) {
                return true;
            }

            // 向队列中添加左右子节点
            if (node.left != null) {
                queue.offer(new Pair<>(node.left, currentSum + node.left.val));
            }
            if (node.right != null) {
                queue.offer(new Pair<>(node.right, currentSum + node.right.val));
            }
        }

        // 如果遍历完队列仍然没有找到符合条件的路径
        return false;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

求根节点到叶节点的数字之和

递归-无返回值

  • 递归结束：节点为空。
  • 递归计算左子树数字、右子树数字，求和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    int ans = 0;

    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private void dfs(TreeNode root, int curNum) {
        if (root == null) {
            return;
        }

        curNum = curNum * 10 + root.val;
        // 如果是叶子节点
        if (root.left == root.right) {
            ans += curNum;
            return;
        }
        
        dfs(root.left, curNum);
        dfs(root.right, curNum);
    }
}

递归-有返回值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int curNum) {
        if (root == null) {
            return 0;
        }

        curNum = curNum * 10 + root.val;
        // 如果是叶子节点
        if (root.left == root.right) {
            return curNum;
        }
        
        return dfs(root.left, curNum) + dfs(root.right, curNum);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

二叉树中的最大路径和

递归

  1. 定义递归函数，返回值是从当前节点到叶子节点的最大和，其值等于当前节点值+max(左子树最大和，右子树最大和)。
  2. 同时更新最大路径和，区分其与dfs的返回值，它应该等于左子树最大和+右子树最大和+当前节点值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    int ans = Integer.MIN_VALUE;;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 递归计算左右子树最大和，注意如果是负数，那就不算这些节点，直接取0
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));

        // 更新全局最大路径和
        ans = Math.max(ans, left + right + root.val);

        return root.val + Math.max(left, right);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

二叉搜索树迭代器

递归

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
class BSTIterator {

    private int idx;
    private List<Integer> arr;

    public BSTIterator(TreeNode root) {
        idx = 0;
        arr = new ArrayList<>();
        inorderTraversal(root);
    }
    
    public int next() {
        return arr.get(idx++);
    }
    
    public boolean hasNext() {
        return idx < arr.size();
    }

    private void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        arr.add(root.val);
        inorderTraversal(root.right);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

迭代

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
class BSTIterator {

    private TreeNode cur;
    private Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        cur = root;
        stack = new ArrayDeque<>();
    }
    
    public int next() {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        int res = cur.val;
        cur = cur.right;
        return res;
    }
    
    public boolean hasNext() {
        return cur != null || !stack.isEmpty();
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

完全二叉树的节点个数

递归

  • 递归结束：如果节点为空，返回0.
  • 递归计算左右子树，加1.
1
2
3
4
5
6
7
8
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

二分查找+位运算

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
58
59
60
class Solution {
    // 计算完全二叉树的节点数
    public int countNodes(TreeNode root) {
        // 如果树为空，节点数为0
        if (root == null) {
            return 0;
        }

        // 计算树的深度（height），从根节点一直向左走
        int level = 0;
        TreeNode node = root;
        while (node.left != null) {
            level++;
            node = node.left; // 一直沿着左子树遍历，直到到达最左的叶子节点
        }

        // low 和 high 表示最后一层的节点编号范围
        // 2^level 是最后一层最小编号，(2^(level+1) - 1) 是最后一层最大编号
        int low = 1 << level; // 2^level
        int high = (1 << (level + 1)) - 1; // 2^(level+1) - 1

        // 使用二分查找来确定最后一层的节点数量
        while (low < high) {
            // 计算中间节点编号
            int mid = (high - low + 1) / 2 + low;
            // 检查编号为 mid 的节点是否存在
            if (exists(root, level, mid)) {
                // 如果节点存在，则说明低位的节点编号存在，移动 low
                low = mid;
            } else {
                // 如果节点不存在，则说明高位的节点编号存在，移动 high
                high = mid - 1;
            }
        }
        // 最终的 low 就是节点总数
        return low;
    }

    // 判断完全二叉树中，编号为 k 的节点是否存在
    public boolean exists(TreeNode root, int level, int k) {
        // 从树的根开始，检查路径是否存在
        int bits = 1 << (level - 1); // 2^(level-1)，用于判断该节点的路径
        TreeNode node = root;

        // 根据二进制位来决定向左还是向右走
        while (node != null && bits > 0) {
            if ((bits & k) == 0) {
                // 如果 k 对应的位是 0，则走左子树
                node = node.left;
            } else {
                // 如果 k 对应的位是 1，则走右子树
                node = node.right;
            }
            bits >>= 1; // 移动到下一个二进制位
        }

        // 如果最后到达的节点不是 null，则说明节点存在
        return node != null;
    }
}
  • 时间复杂度：$O(h^2)$
  • 空间复杂度：O(1)

二叉树的最近公共祖先

递归

  • 遍历树，如果当前节点为空，或者等于p或q，则最近公共祖先就是该节点本身；
  • 否则递归遍历左右子树，如果得到的左右公共祖先都不为空，说明p、q分列左右子树，那么当前节点就是最近公共祖先；
  • 否则p、q同位于左子树或者同位于右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        // 递归查找左右子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 分列于左右子树
        if (left != null && right != null) {
            return root;
        }
        // 位于左子树或右子树
        return left == null ? right : left;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

二叉树的右视图

递归

找每一层最右边的节点：

  1. 用一个变量记录当前遍历到的深度，如果当前结果数组的大小等于深度，说明是首次到达该深度，将当前节点加入结果集。
  2. 先递归遍历右子树，再递归遍历左子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<Integer> ans = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    void dfs(TreeNode root, int depth) {
        // 递归结束
        if (root == null) {
            return;
        }
        // 首次到达depth
        if (ans.size() == depth) {
            ans.add(root.val);
        }
        // 先递归右子树，再递归左子树
        dfs(root.right, depth + 1);
        dfs(root.left, depth + 1);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

迭代

用队列实现层序遍历，将每一层最后一个结点加入结果集。

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
class Solution {
    List<Integer> ans = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                if (node.left != null) {
                    que.add(node.left);
                }
                if (node.right != null) {
                    que.add(node.right);
                }
                if (i == size - 1) {
                    ans.add(node.val);
                }
            }
        }

        return ans;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

二叉树的层平均值

迭代

计算每一层的和/节点个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);

        while (!que.isEmpty()) {
            int n = que.size();
            long sum = 0;
            for (int i = 0; i < n; i++) {
                TreeNode node = que.poll();
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
                sum += node.val;
            }
            ans.add(sum * 1.0 / n);
        }

        return ans;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

注意sum要用long防止溢出。

二叉树的锯齿形层序遍历

层序遍历

把奇数层节点逆转即可。

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
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            int n = que.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode node = que.poll();
                tmp.add(node.val);
                if (node.left != null) {
                    que.offer(node.left);
                }
                if (node.right != null) {
                    que.offer(node.right);
                }
            }
            // 从右到左
            if (ans.size() % 2 == 1) {
                Collections.reverse(tmp);
            }
            ans.add(tmp);
        }

        return ans;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

二叉搜索树的最小绝对差

深度优先搜索

把数字排序后，最小差值一定是相邻两个数的差值。由于二叉搜索树的中序遍历得到的序列是有序的，我们可以计算中序遍历中的相邻两数的差值，取最小值，即为答案。

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
class Solution {
    int ans = Integer.MAX_VALUE;
    int pre = -1;

    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return ans;
    }

    void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);

        if (pre == -1) {
            pre = root.val;
        } else {
            ans = Math.min(ans, root.val - pre);
            pre = root.val;
        }
        
        dfs(root.right);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

二叉搜索树中第K小的元素

深度优先搜索

  1. 中序遍历：递归遍历二叉树的左子树、访问根节点、然后遍历右子树。
  2. 计数与判断：每访问一个节点，count 就增加。当 count == k 时，表示当前节点是我们要找的第 k 小节点。
  3. 提前结束：一旦找到了第 k 小的元素，就不再继续递归，直接返回结果。
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
class Solution {
    private int count = 0; // 用来记录当前遍历到的节点数
    private int result = -1; // 存储第 k 小的值

    public int kthSmallest(TreeNode root, int k) {
        dfs(root, k);
        return result;
    }

    private void dfs(TreeNode root, int k) {
        if (root == null || result != -1) {
            return;
        }

        // 遍历左子树
        dfs(root.left, k);
        
        // 访问当前节点
        count++;
        if (count == k) {
            result = root.val;
            return;
        }

        // 遍历右子树
        dfs(root.right, k);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

验证二叉搜索树

做一次错一次，例如虽然左子树节点值小于父节点值，右子树节点值大于父节点值，但没有检查左子树和右子树的节点是否满足这些范围限制。

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValid(TreeNode root, long left, long right) {
        if (root == null) {
            return true;
        }
        long x = root.val;
        return left < x && x < right && isValid(root.left, left, x) && isValid(root.right, x, right);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    private long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left) || root.val <= pre) {
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
算法笔记 > 二叉树
#二叉树
面试经典 150 题-二叉树
http://example.com/2025/01/15/posts/hot150-9/
作者
Xuan Yang
发布于
2025年1月15日
许可协议