面试题04.06.后继者

链接：面试题04.06.后继者
难度：Medium
标签：树、深度优先搜索、二叉搜索树、二叉树
简介：返回能够访问所有节点的最短路径的长度。

题解 1 - javascript

• 编辑时间：2021-08-06
• 执行用时：96ms
• 内存消耗：47.5MB
• 编程语言：javascript
• 解法介绍：找右侧最左，或者父节点的左子节点是目标节点的父节点。

var inorderSuccessor = function (root, p) {
  if (root === null) return null;
  const parentList = [];
  return successor(find(root, p));
  function find(node, target) {
    if (node === target) return node;
    parentList.push(node);
    let ans;
    if (node.val < target.val) {
      ans = find(node.right, target, node);
    } else {
      ans = find(node.left, target, node);
    }
    if (ans) {
      return ans;
    } else {
      parentList.pop();
      return null;
    }
  }
  function successor(node) {
    if (node.right === null) {
      console.log(parentList);
      if (parentList.length === 0) return null;
      let cur = node;
      for (let i = parentList.length - 1; i >= 0; i--) {
        const parent = parentList[i];
        if (parent.left === cur) {
          return parent;
        } else {
          cur = parent;
        }
      }
      return null;
    }
    let ans = node.right;
    while (ans.left) ans = ans.left;
    return ans;
  }
};

题解 2 - javascript

• 编辑时间：2021-08-07
• 执行用时：96ms
• 内存消耗：47.5MB
• 编程语言：javascript
• 解法介绍：中序遍历。

var inorderSuccessor = function (root, p) {
  let pre;
  return inorder(root, p);
  function inorder(node, p) {
    if (node === null) return null;
    let ans;
    ans = inorder(node.left, p);
    if (ans) return ans;
    if (pre === p) return node;
    pre = node;
    ans = inorder(node.right, p);
    if (ans) return ans;
    return null;
  }
};

题解 3 - cpp

• 编辑时间：2022-05-16
• 执行用时：32ms
• 内存消耗：22.4MB
• 编程语言：cpp
• 解法介绍：递归。

class Solution {
   public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (root == p) {
            if (p->right == nullptr) return nullptr;
            TreeNode* next = p->right;
            while (next->left) next = next->left;
            return next;
        }
        TreeNode* nextRoot = root->val > p->val ? root->left : root->right;
        TreeNode* next = inorderSuccessor(nextRoot, p);
        if (next == nullptr && nextRoot == root->left) next = root;
        return next;
    }
};