thumbnail
HOT100-二叉树汇总
|
算法
|
阅读次
|
3.1k 字
|
14 分钟

二叉树集合

1.二叉树的中序遍历

链接：94. 二叉树的中序遍历 - 力扣（LeetCode）

代码：

法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
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
/**
 * 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 {
    // 用于存储中序遍历的结果
    List<Integer> ans;

    public List<Integer> inorderTraversal(TreeNode root) {
        // 初始化结果集合
        ans = new ArrayList<>();

        // 从根节点开始进行中序遍历
        dfs(root);

        // 返回遍历结果
        return ans;
    }

    /**
     * 递归实现中序遍历
     *
     * 中序遍历顺序：
     * 左子树 -> 根节点 -> 右子树
     */
    private void dfs(TreeNode root) {
        // 递归终止条件：当前节点为空，直接返回
        if (root == null) {
            return;
        }

        // 1. 先遍历左子树
        dfs(root.left);

        // 2. 再访问当前节点
        ans.add(root.val);

        // 3. 最后遍历右子树
        dfs(root.right);
    }
}

法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
/**
 * 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<Integer> inorderTraversal(TreeNode root) {
        // 中序遍历顺序：左 -> 根 -> 右

        // 用于存放遍历结果
        List<Integer> ans = new ArrayList<Integer>();

        // 栈：用来模拟递归过程
        Deque<TreeNode> stk = new LinkedList<TreeNode>();

        // 当当前节点不为空，或者栈中还有未处理的节点时，继续遍历
        while (root != null || !stk.isEmpty()) {

            // 1. 一直向左走，把沿途节点入栈
            // 因为中序遍历要先访问左子树
            while (root != null) {
                stk.push(root);
                root = root.left;
            }

            // 2. 左边走到底后，弹出栈顶节点
            // 这个节点就是当前应该访问的“根节点”
            root = stk.pop();

            // 访问当前节点
            ans.add(root.val);

            // 3. 转向右子树
            // 右子树也按照 左 -> 根 -> 右 的顺序处理
            root = root.right;
        }

        // 返回中序遍历结果
        return ans;
    }
}

法3：Morris中序遍历

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
```

## 2.二叉树的最大深度

**链接：**[104. 二叉树的最大深度 - 力扣（LeetCode）](https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked)

**代码**：

法1：DFS

```java
/**
 * 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;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; // 树的深度=Math.max(左子树深度，右子树深度)+1
    }
}

法2：BFS

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
/**
 * 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) {
        // 如果根节点为空，说明树的深度为 0
        if (root == null) {
            return 0;
        }

        // 队列：用于层序遍历
        Queue<TreeNode> q = new LinkedList<>();

        // 先把根节点加入队列
        q.offer(root);

        // ans 用来记录二叉树的深度
        int ans = 0;

        // 只要队列不为空，就说明还有节点没有遍历
        while (!q.isEmpty()) {
            // 当前层的节点个数
            int sz = q.size();

            // 遍历当前这一层的所有节点
            while (sz-- > 0) {
                // 取出当前层的一个节点
                TreeNode cur = q.poll();

                // 如果左子节点不为空，加入队列
                if (cur.left != null) {
                    q.offer(cur.left);
                }

                // 如果右子节点不为空，加入队列
                if (cur.right != null) {
                    q.offer(cur.right);
                }
            }

            // 当前层遍历完，深度 +1
            ans++;
        }

        // 返回最大深度
        return ans;
    }
}

3.翻转二叉树

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

代码：

法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
/**
 * 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 TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode tmp = root.left; // 暂存root.left
        root.left = invertTree(root.right); // 左 = tmp
        root.right = invertTree(tmp); // 右 = tmp
        return root;
    }
}

法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
class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 空树直接返回 null
        if (root == null) {
            return null;
        }

        // 用 Deque 作为栈，模拟 DFS
        Deque<TreeNode> stk = new LinkedList<>();

        // 先把根节点入栈
        stk.push(root);

        // 栈不为空，说明还有节点没有处理
        while (!stk.isEmpty()) {
            // 取出当前节点
            TreeNode cur = stk.pop();

            // 交换当前节点的左右子树
            TreeNode tmp = cur.left;
            cur.left = cur.right;
            cur.right = tmp;

            // 左子节点不为空，加入栈
            if (cur.left != null) {
                stk.push(cur.left);
            }

            // 右子节点不为空，加入栈
            if (cur.right != null) {
                stk.push(cur.right);
            }
        }

        // 返回翻转后的根节点
        return root;
    }
}

4.对称二叉树

链接：101. 对称二叉树 - 力扣（LeetCode）

代码：

法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
26
27
28
29
30
31
class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 如果根节点为空，空树也是对称的
        // 否则判断根节点的左子树和右子树是否互为镜像
        return root == null || recur(root.left, root.right);
    }

    /**
     * 判断两个子树是否互为镜像
     *
     * L 表示左子树中的一个节点
     * R 表示右子树中的一个节点
     */
    boolean recur(TreeNode L, TreeNode R) {
        // 如果两个节点都为空，说明当前这一对节点是对称的
        if (L == null && R == null) {
            return true;
        }

        // 如果只有一个为空，说明结构不对称
        // 如果两个节点值不相等，说明值不对称
        if (L == null || R == null || L.val != R.val) {
            return false;
        }

        // 继续判断镜像位置：
        // L 的左孩子 要和 R 的右孩子 对称
        // L 的右孩子 要和 R 的左孩子 对称
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}

5.二叉树的直径

链接：543. 二叉树的直径 - 力扣（LeetCode）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private int ans;

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

    // 返回 node 子树的最大链长
    private int dfs(TreeNode node) {
        if (node == null) {
            return -1; // 对于叶子来说，链长就是 -1+1=0
        }
        int lLen = dfs(node.left) + 1; // 左子树最大链长+1
        int rLen = dfs(node.right) + 1; // 右子树最大链长+1
        ans = Math.max(ans, lLen + rLen); // 两条链拼成路径
        return Math.max(lLen, rLen); // 当前子树最大链长
    }
}

6.二叉树的层序遍历

链接：102. 二叉树的层序遍历 - 力扣（LeetCode）

代码：

纯正的bfs

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
61
62
63
64
65
66
67
/**
 * 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) {
        // ans 用来存放最终结果
        // 每一层对应一个 List<Integer>
        List<List<Integer>> ans = new ArrayList<>();

        // 如果根节点为空，直接返回空集合
        if (root == null) {
            return ans;
        }

        // 队列：用于层序遍历
        Deque<TreeNode> q = new LinkedList<>();
        
        // 先把根节点加入队列
        q.offer(root);

        // 只要队列不为空，就继续遍历
        while (!q.isEmpty()) {
            // 当前层的节点值
            List<Integer> curList = new ArrayList<>();

            // 当前层的节点个数
            int sz = q.size();

            // 遍历当前这一层的所有节点
            while (sz-- > 0) {
                // 从队头取出一个节点
                TreeNode cur = q.poll();

                // 记录当前节点的值
                curList.add(cur.val);

                // 如果左子节点不为空，加入队尾
                if (cur.left != null) {
                    q.offer(cur.left);
                }

                // 如果右子节点不为空，加入队尾
                if (cur.right != null) {
                    q.offer(cur.right);
                }
            }

            // 当前层遍历完，加入结果集
            ans.add(curList);
        }

        // 返回层序遍历结果
        return ans;
    }
}

7.将有序数组转换为二叉搜索树

链接：108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

代码：

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
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 从整个数组范围开始递归构建二叉搜索树
        return dfs(nums, 0, nums.length - 1);
    }

    /**
     * 在 nums[l, r] 这个区间内构建一棵平衡二叉搜索树
     *
     * 核心思想：
     * 1. 选择中间元素作为根节点
     * 2. 左半部分构建左子树
     * 3. 右半部分构建右子树
     */
    private TreeNode dfs(int[] nums, int l, int r) {
        // 如果左边界大于右边界，说明当前区间为空
        // 空区间无法构建节点，返回 null
        if (l > r) {
            return null;
        }

        // 选择当前区间的中间位置
        // 这样可以保证左右子树节点数量尽量接近
        int mid = l + (r - l) / 2;

        // 用中间元素创建当前根节点
        TreeNode node = new TreeNode(nums[mid]);

        // 用左半部分递归构建左子树
        node.left = dfs(nums, l, mid - 1);

        // 用右半部分递归构建右子树
        node.right = dfs(nums, mid + 1, r);

        // 返回当前子树的根节点
        return node;
    }
}

8.验证二叉树

链接：98. 验证二叉搜索树 - 力扣（LeetCode）

代码：

中序遍历即可

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
61
62
/**
 * 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 {
    // pre 用来记录中序遍历过程中，当前节点的前一个节点
    TreeNode pre = null;

    public boolean isValidBST(TreeNode root) {
        // 空树也是合法的二叉搜索树
        if (root == null) {
            return true;
        }

        // 通过中序遍历判断是否严格递增
        return dfs(root);
    }

    /**
     * 中序遍历判断 BST 是否合法
     *
     * 二叉搜索树的性质：
     * 左子树所有节点 < 当前节点 < 右子树所有节点
     *
     * 所以 BST 的中序遍历结果应该是严格递增的
     */
    private boolean dfs(TreeNode root) {
        // 当前节点为空，说明这条路径合法
        if (root == null) {
            return true;
        }

        // 1. 先递归判断左子树
        if (!dfs(root.left)) {
            return false;
        }

        // 2. 访问当前节点
        // 如果前一个节点的值 >= 当前节点的值
        // 说明中序遍历不是严格递增，BST 不合法
        if (pre != null && pre.val >= root.val) {
            return false;
        }

        // 更新 pre，让当前节点成为下一个节点的“前一个节点”
        pre = root;

        // 3. 最后递归判断右子树
        return dfs(root.right);
    }
}

9.二叉搜索树中第k小的树

链接：230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

代码：

法1：中序遍历第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
29
30
class Solution {
    int ans = -1;
    int count = 0; // 全局计数器：记录我是第几个被“中序访问”到的

    private void dfs(TreeNode root, int k) {
        // 剪枝：如果节点为空，或者已经找到答案，直接返回
        if (root == null || ans != -1) {
            return;
        }

        // 1. 走左边（去拿更小的）
        dfs(root.left, k);

        // 2. 处理中间（当前节点）
        // 这里是中序遍历的核心，节点是按照从小到大的顺序执行这里的
        count++; 
        if (count == k) {
            ans = root.val;
            return; // 找到了，收工
        }

        // 3. 走右边（去拿更大的）
        dfs(root.right, k);
    }

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

10.二叉树的右视图

链接：199. 二叉树的右视图 - 力扣（LeetCode）

代码：

法1：BFS取最后一个即可（或改变添加顺序取第一个）

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
61
62
63
64
class Solution {

    /**
     * 二叉树的右视图
     *
     * 思路：
     * 使用层序遍历，也就是 BFS。
     * 每一层从右往左遍历，所以每一层第一个访问到的节点，
     * 就是从右侧能看到的节点。
     */
    public List<Integer> rightSideView(TreeNode root) {
        // 如果根节点为空，直接返回空集合
        if (root == null) {
            return new ArrayList<>();
        }

        // 保存右视图结果
        List<Integer> ans = new ArrayList<>();

        // 队列用于层序遍历
        Queue<TreeNode> q = new LinkedList<>();

        // 先把根节点加入队列
        q.add(root);

        // 只要队列不为空，就继续遍历
        while (q.size() > 0) {
            // 当前层的节点数量
            int sz = q.size();

            // 标记当前层是否还没有加入过右视图节点
            // 因为我们是从右往左加入队列，所以每层第一个节点就是最右侧节点
            boolean vis = true;

            // 遍历当前层的所有节点
            while (sz-- > 0) {
                // 取出队头节点
                TreeNode cur = q.poll();

                // 如果是当前层第一个访问到的节点，就加入答案
                if (vis) {
                    ans.add(cur.val);
                }

                // 当前层已经加入过右视图节点，后面的节点不再加入
                vis = false;

                // 先加入右子节点
                // 这样下一层遍历时，会优先访问右侧节点
                if (cur.right != null) {
                    q.add(cur.right);
                }

                // 再加入左子节点
                if (cur.left != null) {
                    q.add(cur.left);
                }
            }
        }

        // 返回右视图结果
        return ans;
    }
}

11.二叉树展开为链表

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

代码：

法1：

1

评论区

欢迎留下你的想法

评论系统还没有接入配置，界面已经预留好了。

上一篇
下一篇

CHENYE ARCHIVE

进入信号层

正在接入这片属于我的信号层

早上好！