递归，迭代右子节点（新建递归函数 / 使用原函数），3 解法，求解《998. 最大二叉树 II》

代码数据结构:树数据结构:二叉树数据结构:最大树专题:最大树算法:递归算法:迭代语言:JavaScript 语言:Go 语言:PHP 语言:Python 语言:C 语言:C++语言:C#语言:TypeScript 语言:Java

2022-08-30 12:35:44

递归，迭代右子节点（新建递归函数 / 使用原函数），3 解法，求解《998. 最大二叉树 II》

例题

998. 最大二叉树 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 。
请注意，题目没有直接给出 a ，只是给出一个根节点 root = Construct(a) 。
假设 b 是 a 的副本，并在末尾附加值 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

思路

附加值始终在列表末尾，只可能是

比它大的节点的右子节点
- 不可能位于已知节点的左子节点（否则已知节点在它右边，与它是列表末尾相悖）
比它小的节点是它的左子节点

答案

递归 · 新建递归函数

var insertIntoMaxTree = function(root, val) { // 可选链操作符 ?.
  if (root.val < val) return new TreeNode(val, root)
  ;(function d(n) {
    if (n.right?.val > val) return d(n.right)
    n.right = new TreeNode(val, n.right)
  })(root)
  return root
};

function insertIntoMaxTree(root: TreeNode | null, val: number): TreeNode | null {
  const d = n => n.right?.val > val ? d(n.right) : n.right = new TreeNode(val, n.right)
  return root.val < val ? new TreeNode(val, root) : (d(root), root)
};

class Solution {
  function d($n, $val) {
    if ($n->right && $n->right->val > $val) return $this->d($n->right, $val);
    $n->right = new TreeNode($val, $n->right);
  }
  function insertIntoMaxTree($root, $val) {
    if ($root->val < $val) return new TreeNode($val, $root);
    $this->d($root, $val);
    return $root;
  }
}

func d(n *TreeNode, val int) {
  if n.Right != nil && n.Right.Val > val {
    d(n.Right, val)
    return
  }
  n.Right = &TreeNode{val, n.Right, nil}
}
func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
  if root.Val < val {
    return &TreeNode{val, root, nil}
  }
  d(root, val)
  return root
}

class Solution {
  public void d(TreeNode n, int val) {
    if (n.right != null && n.right.val > val) d(n.right, val);
    else n.right = new TreeNode(val, n.right, null);
  }
  public TreeNode insertIntoMaxTree(TreeNode root, int val) {
    if (root.val < val) return new TreeNode(val, root, null);
    d(root, val);
    return root;
  }
}

public class Solution {
  public void D(TreeNode n, int val) {
    if (n.right != null && n.right.val > val) D(n.right, val);
    else n.right = new TreeNode(val, n.right);
  }
  public TreeNode InsertIntoMaxTree(TreeNode root, int val) {
    if (root.val < val) return new TreeNode(val, root);
    D(root, val);
    return root;
  }
}

void d(struct TreeNode* n, int val) {
  if (n->right && n->right->val > val) return d(n->right, val);
  struct TreeNode* obj = malloc(sizeof(struct TreeNode));
  obj->val = val;
  obj->left = n->right;
  obj->right = NULL;
  n->right = obj;
}
struct TreeNode* insertIntoMaxTree(struct TreeNode* root, int val){
  if (root->val < val) {
    struct TreeNode* obj = malloc(sizeof(struct TreeNode));
    obj->val = val;
    obj->left = root;
    obj->right = NULL;
    return obj;
  }
  d(root, val);
  return root;
}

class Solution:
  def d(self, n: Optional[TreeNode], val: int):
    if n.right and n.right.val > val: return self.d(n.right, val)
    n.right = TreeNode(val, n.right)
  def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if root.val < val: return TreeNode(val, root)
    self.d(root, val)
    return root

递归 · 使用原函数

var insertIntoMaxTree = function(root, val) {
  if (root === null || root.val < val) return new TreeNode(val, root)
  root.right = insertIntoMaxTree(root.right, val)
  return root
};

function insertIntoMaxTree(root: TreeNode | null, val: number): TreeNode | null {
  if (root == null || root.val < val) return new TreeNode(val, root)
  root.right = insertIntoMaxTree(root.right, val)
  return root
};

class Solution {
  function insertIntoMaxTree($root, $val) {
    if ($root === null || $root->val < $val) return new TreeNode($val, $root);
    $root->right = $this->insertIntoMaxTree($root->right, $val);
    return $root;
  }
}

func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
  if root == nil || root.Val < val {
    return &TreeNode{val, root, nil}
  }
  root.Right = insertIntoMaxTree(root.Right, val)
  return root
}

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

public class Solution {
  public TreeNode InsertIntoMaxTree(TreeNode root, int val) {
    if (root == null || root.val < val) return new TreeNode(val, root);
    root.right = InsertIntoMaxTree(root.right, val);
    return root;
  }
}

struct TreeNode* insertIntoMaxTree(struct TreeNode* root, int val){
  if (root == NULL || root->val < val) {
    struct TreeNode* obj = malloc(sizeof(struct TreeNode));
    obj->val = val;
    obj->left = root;
    obj->right = NULL;
    return obj;
  }
  root->right = insertIntoMaxTree(root->right, val);
  return root;
}

class Solution:
  def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if root == None or root.val < val: return TreeNode(val, root)
    root.right = self.insertIntoMaxTree(root.right, val)
    return root

迭代


var insertIntoMaxTree = function(root, val) {
  if (root.val < val) return new TreeNode(val, root)
  const r = root
  while (root.right?.val > val) root = root.right
  root.right = new TreeNode(val, root.right)
  return r
};


var insertIntoMaxTree = function(root, val) {
  const r = root
  while (root.right?.val > val) root = root.right
  return root.val < val ? new TreeNode(val, root) : (root.right = new TreeNode(val, root.right), r)
};

class Solution {
  function insertIntoMaxTree($root, $val) {
    if ($root->val < $val) return new TreeNode($val, $root);
    $r = $root;
    while ($root->right && $root->right->val > $val) $root = $root->right;
    $root->right = new TreeNode($val, $root->right);
    return $r;
  }
}

func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
  if root.Val < val {
    return &TreeNode{val, root, nil}
  }
  r := root
  for root.Right != nil && root.Right.Val > val {
    root = root.Right
  }
  root.Right = &TreeNode{val, root.Right, nil}
  return r
}

class Solution {
  public TreeNode insertIntoMaxTree(TreeNode root, int val) {
    if (root.val < val) return new TreeNode(val, root, null);
    TreeNode r = root;
    while (root.right != null && root.right.val > val) root = root.right;
    root.right = new TreeNode(val, root.right, null);
    return r;
  }
}

public class Solution {
  public TreeNode InsertIntoMaxTree(TreeNode root, int val) {
    if (root.val < val) return new TreeNode(val, root);
    TreeNode r = root;
    while (root.right != null && root.right.val > val) root = root.right;
    root.right = new TreeNode(val, root.right);
    return r;
  }
}

struct TreeNode* insertIntoMaxTree(struct TreeNode* root, int val){
  if (root->val < val) {
    struct TreeNode* obj = malloc(sizeof(struct TreeNode));
    obj->val = val;
    obj->left = root;
    obj->right = NULL;
    return obj;
  }
  struct TreeNode* r = root;
  while (root->right && root->right->val > val) root = root->right;
  struct TreeNode* obj = malloc(sizeof(struct TreeNode));
  obj->val = val;
  obj->left = root->right;
  obj->right = NULL;
  root->right = obj;
  return r;
}

class Solution:
  def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if root.val < val: return TreeNode(val, root)
    r = root
    while root.right and root.right.val > val: root = root.right
    root.right = TreeNode(val, root.right)
    return r

Shon

Github　力扣　 M站　全部原创，请勿转载

递归、迭代、前序遍历，3 解法，求解《669. 修剪二叉搜索树》

后序遍历，递归和迭代 2 种算法，用哈希映射数据结构，字符串或元组构造键名，用序列化技巧，求解《652. 寻找重复的子树》

后序遍历，递归和迭代 2 种算法，用哈希映射数据结构，字符串 / 元组构造键名，用序列化技巧，求解《652. 寻找重复的子树》

递归、动态规划、二分查找、贪心算法，升序排列数组，传递回调函数，自定义排序，4 解法求解《646. 最长数对链》