面试题 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}
 */
var inorderSuccessor = function (root, p) {
  const list = [];
  inorder(root, list);
  return list[list.findIndex(item => item.val === p.val) + 1];
};

const 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}
 */
var inorderSuccessor = function (root, p) {
  if (root == null) return null;
  if (root.val <= p.val) return inorderSuccessor(root.right, p);
  let ans = inorderSuccessor(root.left, p);
  return ans == null ? root : ans;
};