面试题 04.06. 后继者

面试题 04.06. 后继者

leetcode 链接

解法一：中序遍历

中序遍历把节点保存在数组中，最后返回对应的结果。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @return {TreeNode}
 */
function inorderSuccessor(root, p) {
  const list = []
  inorder(root, list)
  return list[list.findIndex(item => item.val === p.val) + 1]
}

function inorder(root, list) {
  if (root) {
    inorder(root.left, list)
    list.push(root)
    inorder(root.right, list)
  }
}

解法二：BST 特性 + 递归

解题链接

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @return {TreeNode}
 */
function inorderSuccessor(root, p) {
  if (root == null)
    return null
  if (root.val <= p.val)
    return inorderSuccessor(root.right, p)
  const ans = inorderSuccessor(root.left, p)
  return ans == null ? root : ans
}