998.最大二叉树 II

问题

最大树定义：一个树，其中每个节点的值都大于其子树中的任何其他值。

给出最大树的根节点 $root$。

就像之前的问题那样，给定的树是从表 $A(root=Construct(A))$递归地使用下述 $Construct(A)$ 例程构造的：

• 如果 $A$ 为空，返回 $null$
• 否则，令 $A[i]$ 作为 $A$ 的最大元素。创建一个值为 $A[i]$ 的根节点 $root$
• $root$ 的左子树将被构建为 $Construct([A[0],A[1],...,A[i-1]])$
• $root$ 的右子树将被构建为 $Construct([A[i+1],A[i+2],...,A[A.length-1]])$
• 返回 $root$ 请注意，我们没有直接给定 $A$，只有一个根节点 $root=Construct(A)$.

假设 $B$ 是 $A$ 的副本，并附加值 $val$。保证 $B$ 中的值是不同的。

返回 $Construct(B)$。

示例 1：

graph TD
    A[4] --> B[1]
    A --> C[3]
    B --> D[ ]
    B --> E[ ]
    C --> F[2]
    C --> G[ ]
    
    style D fill:transparent,stroke:transparent
    style E fill:transparent,stroke:transparent
    style G fill:transparent,stroke:transparent

graph TD
    A[5] --> B[4]
    A --> C[ ]
    B --> D[1]
    B --> E[3]
    E --> F[2]
    E --> G[ ]
    
    style C fill:transparent,stroke:transparent
    style G fill:transparent,stroke:transparent

输入： $root=[4,1,3,null,null,2],val=5$ 输出： $[5,4,null,1,3,null,null,2]$ 解释： $A=[1,4,2,3],B=[1,4,2,3,5]$

示例 2：

graph TD
    A[5] --> B[2]
    A --> C[4]
    B --> D[ ]
    B --> E[1]
    
    style D fill:transparent,stroke:transparent

graph TD
    A[5] --> B[2]
    A --> C[4]
    B --> D[ ]
    B --> E[1]
    C --> F[ ]
    C --> G[3]
    
    style D fill:transparent,stroke:transparent
    style F fill:transparent,stroke:transparent

输入：$root=[5,2,4,null,1],val=3$ 输出：$[5,2,4,null,1,null,3]$ 解释：$A=[2,1,5,4],B=[2,1,5,4,3]$

示例 3：

graph TD
    A[5] --> B[2]
    A --> C[3]
    B --> D[ ]
    B --> E[1]
    
    style D fill:transparent,stroke:transparent

graph TD
    A[5] --> B[2]
    A --> C[4]
    B --> D[ ]
    B --> E[1]
    C --> F[3]
    C --> G[ ]
    
    style D fill:transparent,stroke:transparent
    style G fill:transparent,stroke:transparent

输入：$root=[5,2,3,null,1],val=4$ 输出：$[5,2,4,null,1,3]$ 解释：$A=[2,1,5,3],B=[2,1,5,3,4]$

解法

这道题本身不难，难得是理解题意，一开始我还在想示例2中的3放在5前面似乎也并无不可。后来才发现，其实$val$是追加在$A$末尾的，而不是随便放在哪个位置的。既然这样，考虑一下$val$与$root$的大小关系，一共有三种情况:

1. $root$为空，此时直接生成一个TreeNode(val)返回即可
2. $root.val<val$，此时说明，$val$已经找到了应该在的位置,那么生成一个TreeNode(val), 并且将左儿子设置成$root$（因为$root$对应的数组元素必然在$val$的左边。）
3. $root.val>val$,此时说明，$val$仍然没有找到所在位置，但是因为$val$在最右，那么递归到$root.right$中去处理。

递归完成后返回root即可。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        // 情况1
        if (root == null) {
            return new TreeNode(val);
        }
        // 情况2
        if (root.val < val) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        // 情况3
        root.right = insertIntoMaxTree(root.right,val);
        //最终递归返回
        return root;
    }
}