最大二叉树 II 图解题解

这道题到底在问什么

输入

a = 30,80,20,60，val = 70

输出

80 的右孩子由 60 变成 70，60 子树挂到 70 左边

最优解：一步一步想明白

1. 3记住这句口诀:追加在末尾,只走右链;比 val 小就让位、比 val 大就继续往右。后面每帧都在套它。
2. 4根 80 最大这是一棵最大树。它的规矩是:每个节点都比自己子树里的所有节点大。所以最大的 80 坐在根上。
3. 580 > 子树一切验证一下:80 比它子树里的 30、60、20 全都大,所以它才有资格当根。这就是最大树最核心的那条规矩。
4. 660 > 20这条规矩一层层往下都成立:右边的 60 也比它子树里的 20 大。每一棵子树都自带同一条规矩。
5. 7a = 30, 80, 20, 60这棵树是从数组 a = 30, 80, 20, 60 用 Construct 建出来的:每次取区间最大值当根,左边的数建左子树,右边的数建右子树。先把数组的样子记牢。
6. 8b = a + 70现在来了新值 70,题目要求把它追加到数组 a 的最末尾,得到 b = 30, 80, 20, 60, 70。我们要的是 b 重新建成的最大树。
7. 9锁定右链 80 → 60关键一步想通就赢了:70 排在数组最末尾,在 Construct 里它永远排在所有现存元素后面,所以只可能挂在某个节点的右边。我们只需沿着根的右链往下找,右链就是 80 到 60 这一串。
8. 10左子树不动左子树 30 这一边完全不用碰。因为 70 在末尾,绝不会跑到现存元素的左边去,注意力全部放在右链上。
9. 1170 与 80 比从根 80 开始下行。拿 70 和 80 比一比:70 能不能比 80 还大、从而取代它当新根?
10. 1270 < 8070 比 80 小,所以 80 稳坐根位不动。70 只能沉进 80 的右子树继续找位置,指针准备滑向它的右孩子。
11. 13指针到 60指针顺着 80 的右指针滑到下一个节点 60,继续往右链深处找它的位置。
12. 1470 与 60 比现在指针来到右孩子 60。再比一次:70 和 60 谁大?
13. 1570 > 6070 比 60 大,插入点就定在这儿!按最大树的规矩,70 要当这一段的新根,原来的 60 得给它让位。
14. 1660 子树整体下移要注意:让位的是 60 连着它下面的 20 这一整棵子树,谁都不能丢。下一步把这整棵挂到新节点 70 的左边。
15. 1770 占 60 原位新建一个节点 70,放到 60 原来的位置上,也就是接在 80 的右边。
16. 1860 子树 → 70 的左刚才让位的 60 加上 20 这一整棵,挂到 70 的左孩子上。因为它们都比 70 小,正好待在 70 的左子树里,规矩一点没破。
17. 1970 右孩子空70 的右孩子是空的。道理也简单:70 是数组最后一个元素,它后面再没有别的数,右边自然空着。
18. 2080 的右 = 70最后把 80 原来指向 60 的那根右指针,改成指向 70。这样新节点 70 就正式接回了整棵树。
19. 21新树成形新的最大树成形了。80 还是根,左边的 30 没动,右边由 60 换成了 70,70 底下挂着 60 和 20。
20. 2280 > 70验证一下规矩有没有破。先看父子:80 > 70,根依然是最大,这一关过了。
21. 2370 > 60 > 20再看 70 这棵子树:70 > 60 > 20,每个节点都比自己子树里的大,完全满足最大树的规矩。
22. 24答案 = 新树回放整个过程:从根 80 沿右链下行,70 一路比下来,到 60 时终于更大,就在那里取代 60、把 60 子树收作左孩子。一次右链下行,插入完成。
23. 25只走右链 O(h)整趟只碰了右链上的 80 和 60 两个节点,没有重建任何子树,这就是增量插入的高效之处。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoMaxTree(
        self, root: Optional[TreeNode], val: int
    ) -> Optional[TreeNode]:
        if root is None or root.val < val:
            return TreeNode(val, root)
        root.right = self.insertIntoMaxTree(root.right, val)
        return root

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if (!root || root->val < val) return new TreeNode(val, root, nullptr);
        root->right = insertIntoMaxTree(root->right, val);
        return root;
    }
};

import java.util.*;
/**
 * 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 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 ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root == null || root.val < val) {
            return new TreeNode(val, root, null);
        }
        root.right = insertIntoMaxTree(root.right, val);
        return root;
    }
}

复杂度

面试官可能追问