最大二叉树 II 图解题解

b 建成的最大树，和原来那棵差在哪

最大树的规矩是：每个节点都比自己子树里的所有数大，所以整棵树里最大的数坐在根上。原树是数组 a 用 Construct 建的，即取区间最大值当根，最大值左边的数建左子树、右边的数建右子树。现在把 val 追加到 a 的末尾得到 b，要你返回 b 重新 Construct 出来的最大树。题面给的是 a=30,80,20,60、val=70。

把数组还原重新 Construct，为什么白费力气

数组末尾多了个 val，一种做法是把 a 拼上 val、整个数组从头 Construct 一遍。可原树已经建好摆在手里，全部重建至少 O(n) 起步，而这趟里绝大多数节点的位置压根不动：追加一个末尾元素，只会撼动树里很小的一段，为它重建整棵树纯属浪费。

新值排在末尾，凭什么只能进右链

回到 Construct 的定义：一个节点的左子树由它前面的元素建、右子树由它后面的元素建。val 放在数组最末尾，排在所有现存元素后面，所以无论哪一层，它都只可能落在某个节点右侧。于是左子树那一整边完全不用碰，只要从根出发、顺着那条一路向右的右链往下找它的落脚点就行。

沿右链下行，遇到比它小的就让位

下行时每到一个节点就拿它和 val 比一次。若当前节点比 val 小，说明 val 该取代它当这一段的新根，于是新建一个值为 val 的节点，把当前节点连着下面整棵子树收作它的左孩子，右孩子留空；原子树里的值都比 val 小，正好待在左边，规矩没破。若当前节点比 val 大，val 还不够格，就钻进它的右子树接着比。写成递归就是：root 为空或 root ＜ val 时返回 TreeNode(val, root)，否则让 root.right 接上右子树的递归结果、返回 root。

a=30,80,20,60 追加 70，右链上走两步

原树里 80 当根，左孩子 30，右孩子 60，60 底下挂着 20，右链就是 80 到 60 这一串。从根 80 起：70 ＜ 80，80 稳坐不动，滑到它的右孩子 60。再比：60 ＜ 70，插入点就定在这儿。新建节点 70，把 60 连着 20 这整棵收作 70 的左孩子，70 的右孩子留空，再把 80 原来指向 60 的右指针改指 70。结果：80 还是根，左边 30 没动，右边由 60 换成 70，70 底下挂着 60 和 20，满足 80 ＞ 70 ＞ 60 ＞ 20。全程只碰了右链上的 80 和 60 两个节点。

比较写反、或把原子树丢了，结果全乱

遇到比 val 小的节点让位时，别把它原来的子树顺手丢了，原子树的值都小于 val，得整棵收进它左边，丢一棵就漏一批数据。比较方向也别写反：只有节点 ＜ val 才让位，写成节点比 val 大才插入，插出来的树整个是错的。复杂度上，只沿右链走一趟，时间是右链长度 O(h)；树退化成一路向右的偏链时右链长 n，最坏 O(n)；递归栈也只在右链上展开，空间同样是 O(h)、最坏 O(n)。另外，val 比根还大时，在根处就让位、原树整棵成了它的左孩子；val 比所有节点都小时，一路走到右链末端、当最右节点的右孩子。

Python

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

C++

#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;
    }
};

Java

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;
    }
}