侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【DFS, 二叉树】最大二叉树 II

GabrielxD
2022-08-30 / 0 评论 / 0 点赞 / 206 阅读 / 692 字
温馨提示:
本文最后更新于 2022-09-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

998. 最大二叉树 II


最大树 定义:一棵树,并满足:其中每个节点的值都大于其子树中的任何其他值。

给你最大树的根节点 root 和一个整数 val

就像 之前的问题 那样,给定的树是利用 Construct(a) 例程从列表 aroot = 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)

假设 ba 的副本,并在末尾附加值 val。题目数据保证 b 中的值互不相同。

返回 Construct(b)

示例 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]

示例 2:

输入: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:

输入: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]

提示:

  • 树中节点数目在范围 [1, 100]
  • 1 <= Node.val <= 100
  • 树中的所有值 互不相同
  • 1 <= val <= 100

解题

方法一:DFS

思路

这题让我们做的事是:把给出的值作为一个新节点插入最大二叉树中,额外的规则是:

  1. 插入节点的位置要遵守最大二叉树的形式。
  2. 尽量向右边插入节点。
  3. 如果树中所有值都比给出的值小,那么把新节点作为根节点,其左子树为原二叉树。

具体做法是从根节点开始递归:

  • 如果当前节点的值小于给定值,把该节点作新节点的左子节点并返回新节点。
  • 如果当前节点的右节点存在,递归地把给定值插入右子树。
  • 如果当前节点的右节点不存在,直接把给定值作当前节点的右节点。

代码

class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if (root->val < val) return new TreeNode(val, root, nullptr);
        root->right = root->right ? insertIntoMaxTree(root->right, val) : new TreeNode(val);
        return root;
    }	
};
class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root.val < val) return new TreeNode(val, root, null);
        root.right = root.right != null ? insertIntoMaxTree(root.right, val) : new TreeNode(val);
        return root;
    }
}
0

评论区