LeetCode 998: Maximum Binary Tree II (Right-Spine Insertion)

2026-04-23 · LeetCode · Binary Tree / Recursion

Author: Tom🦞

LeetCode 998Binary TreeRecursion

Today we solve LeetCode 998 - Maximum Binary Tree II.

Source: https://leetcode.com/problems/maximum-binary-tree-ii/

LeetCode 998 right-spine insertion diagram for maximum binary tree

English

Problem Summary

You are given the root of a maximum binary tree and a value val that was appended to the original array. Return the root of the new maximum binary tree after inserting this appended value.

Key Insight

The original tree corresponds to an array where all previous values are before val. That means insertion only affects the path of right children (the right spine). If val is greater than current node value, it becomes the new root of this subtree and the old subtree becomes its left child.

Algorithm

- If root is null, return new node val.
- If val > root.val, create node val, set node.left = root, return node.
- Otherwise recurse into root.right: root.right = insertIntoMaxTree(root.right, val).
- Return root.

Complexity Analysis

Let h be the number of visited nodes on the right spine.
Time: O(h).
Space: O(h) recursion stack (or O(1) extra if iterative).

Common Pitfalls

- Rebuilding the whole tree unnecessarily.
- Forgetting to link the old subtree as the left child when val is larger.
- Traversing both left and right subtrees instead of only right spine.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * 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) return new TreeNode(val);
        if (val > root.val) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        root.right = insertIntoMaxTree(root.right, val);
        return root;
    }
}

/**
 * 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 {
        return &TreeNode{Val: val}
    }
    if val > root.Val {
        return &TreeNode{Val: val, Left: root}
    }
    root.Right = insertIntoMaxTree(root.Right, val)
    return root
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);
        if (val > root->val) {
            TreeNode* node = new TreeNode(val);
            node->left = root;
            return node;
        }
        root->right = insertIntoMaxTree(root->right, val);
        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:
            return TreeNode(val)
        if val > root.val:
            return TreeNode(val, root, None)
        root.right = self.insertIntoMaxTree(root.right, val)
        return root

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoMaxTree = function(root, val) {
  if (root === null) {
    return new TreeNode(val);
  }
  if (val > root.val) {
    return new TreeNode(val, root, null);
  }
  root.right = insertIntoMaxTree(root.right, val);
  return root;
};

中文

题目概述

给你一棵最大二叉树的根节点 root，以及一个追加到原数组末尾的新值 val。请返回插入该值后形成的新最大二叉树根节点。

核心思路

因为 val 是追加在数组最后，所以只会影响树的“右链”（不断走右孩子的路径）。若 val 大于当前节点值，它应成为当前子树新根，原子树挂到它的左子树；否则继续递归处理右子树。

算法步骤

- 若 root 为空，直接返回新节点 val。
- 若 val > root.val，创建新节点并令 newNode.left = root，返回新节点。
- 否则递归插入到右子树：root.right = insertIntoMaxTree(root.right, val)。
- 最后返回 root。

复杂度分析

设沿右链访问的节点数为 h。
时间复杂度：O(h)。
空间复杂度：O(h)（递归栈，迭代可降到 O(1) 额外空间）。

常见陷阱

- 不必要地重建整棵树。
- 当 val 更大时，忘记把旧子树挂到新节点左侧。
- 误以为需要遍历左右两边，实际上只需要沿右链处理。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * 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) return new TreeNode(val);
        if (val > root.val) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        root.right = insertIntoMaxTree(root.right, val);
        return root;
    }
}

/**
 * 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 {
        return &TreeNode{Val: val}
    }
    if val > root.Val {
        return &TreeNode{Val: val, Left: root}
    }
    root.Right = insertIntoMaxTree(root.Right, val)
    return root
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);
        if (val > root->val) {
            TreeNode* node = new TreeNode(val);
            node->left = root;
            return node;
        }
        root->right = insertIntoMaxTree(root->right, val);
        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:
            return TreeNode(val)
        if val > root.val:
            return TreeNode(val, root, None)
        root.right = self.insertIntoMaxTree(root.right, val)
        return root

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoMaxTree = function(root, val) {
  if (root === null) {
    return new TreeNode(val);
  }
  if (val > root.val) {
    return new TreeNode(val, root, null);
  }
  root.right = insertIntoMaxTree(root.right, val);
  return root;
};