Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/998.html
998. Maximum Binary Tree II (Medium)
We are given the root
node of a maximum tree: a tree where every node has a value greater than any other value in its subtree.
Just as in the previous problem, the given tree was constructed from an list A
(root = Construct(A)
) recursively with the following Construct(A)
routine:
- If
A
is empty, returnnull
. - Otherwise, let
A[i]
be the largest element ofA
. Create aroot
node with valueA[i]
. - The left child of
root
will beConstruct([A[0], A[1], ..., A[i-1]])
- The right child of
root
will beConstruct([A[i+1], A[i+2], ..., A[A.length - 1]])
- Return
root
.
Note that we were not given A directly, only a root node root = Construct(A)
.
Suppose B
is a copy of A
with the value val
appended to it. It is guaranteed that B
has unique values.
Return Construct(B)
.
Example 1:
Input: root = [4,1,3,null,null,2], val = 5 Output: [5,4,null,1,3,null,null,2] Explanation: A = [1,4,2,3], B = [1,4,2,3,5]
Example 2:
Input: root = [5,2,4,null,1], val = 3 Output: [5,2,4,null,1,null,3] Explanation: A = [2,1,5,4], B = [2,1,5,4,3]
Example 3:
Input: root = [5,2,3,null,1], val = 4 Output: [5,2,4,null,1,3] Explanation: A = [2,1,5,3], B = [2,1,5,3,4]
Note:
1 <= B.length <= 100
Companies:
Facebook
Related Topics:
Tree
Similar Questions:
Solution 1.
- Find insertion point: Keep repeating the following logic until
node
becomesNULL
- If
val < node->val
, go right. - Otherwise, break.
- If
- Assume
prev
is the parent ofnode
. The new node should be the right child ofprev
andnode
(which might beNULL
) should be the left child of the new node.
// OJ: https://leetcode.com/problems/maximum-binary-tree-ii/
// Time: O(N)
// Space: O(1)
class Solution {
public:
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
TreeNode *node = root, *prev = NULL;
while (node && val < node->val) {
prev = node;
node = node->right;
}
auto n = new TreeNode(val);
if (prev) prev->right = n;
else root = n;
n->left = node;
return root;
}
};
-
/** * 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) { TreeNode newNode = new TreeNode(val); if (root == null) return newNode; if (val > root.val) { newNode.left = root; return newNode; } TreeNode temp = root; while (temp.val > val) { TreeNode rightChild = temp.right; if (rightChild == null) { temp.right = newNode; break; } else if (rightChild.val < val) { temp.right = newNode; newNode.left = rightChild; break; } else temp = temp.right; } return root; } } ############ /** * 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 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; } }
-
// OJ: https://leetcode.com/problems/maximum-binary-tree-ii/ // Time: O(N) // Space: O(1) class Solution { public: TreeNode* insertIntoMaxTree(TreeNode* root, int val) { TreeNode *node = root, *prev = NULL; while (node && val < node->val) { prev = node; node = node->right; } auto n = new TreeNode(val); if (prev) prev->right = n; else root = n; n->left = node; return root; } };
-
# 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 ############ # 998. Maximum Binary Tree II # https://leetcode.com/problems/maximum-binary-tree-ii/ # 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 and root.val > val: root.right = self.insertIntoMaxTree(root.right, val) return root node = TreeNode(val) node.left = root return node
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ 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 }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function insertIntoMaxTree( root: TreeNode | null, val: number, ): TreeNode | null { if (!root || root.val < val) { return new TreeNode(val, root); } root.right = insertIntoMaxTree(root.right, val); return root; }
-
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; impl Solution { pub fn insert_into_max_tree( mut root: Option<Rc<RefCell<TreeNode>>>, val: i32, ) -> Option<Rc<RefCell<TreeNode>>> { if root.is_none() || root.as_ref().unwrap().as_ref().borrow().val < val { return Some(Rc::new(RefCell::new(TreeNode { val, left: root.take(), right: None, }))); } { let mut root = root.as_ref().unwrap().as_ref().borrow_mut(); root.right = Self::insert_into_max_tree(root.right.take(), val); } root } }