【二叉树】最大二叉树 II
题目描述
最大树 定义：一棵树，并满足：其中每个节点的值都大于其子树中的任何其他值。
给你最大树的根节点 root 和一个整数 val 。
给定的树是利用 Construct(a) 例程从列表 a（root = 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 。
示例1:
输入：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]
解题思路
这道题最难的是理解题目，看了半天没有理解这道题，最后是看了别人的代码实现才知道要怎么做的。
其实就是在树中添加节点：
case1: val > root.val
case2: val < node.val && val > node.right.val
case3: val < node.val && node.right == null
这里直接使用dfs做树的遍历就可以了，dfs遍历代码如下：
import org.example.TreeNode;
class Solution {
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
if (val > root.val) {
TreeNode node = new TreeNode(val);
node.left = root;
return node;
}
dfs(root, val);
return root;
}
private void dfs(TreeNode root, int val) {
if (root.right != null && root.right.val < val) {
root.right = new TreeNode(val, root.right, null);
} else if (root.right == null) {
root.right = new TreeNode(val);
} else {
root = root.right;
dfs(root, val);
}
}
}
总结
这道题是中等难度，重点是理解题目要求，如果有更好的题目描述、更高效更简洁的代码实现欢迎回复。