LCR053.二叉搜索树中的中序后继

链接：LCR053.二叉搜索树中的中序后继
难度：Medium
标签：树、深度优先搜索、二叉搜索树、二叉树
简介：给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

题解 1 - typescript

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

function inorderSuccessor(root: TreeNode | null, p: TreeNode | null): TreeNode | null {
  if (p === null || root === null) return null;
  let prev: TreeNode | null = null;
  let ans: TreeNode | null = null;
  inorder(root);
  return ans;
  function inorder(node: TreeNode | null): boolean {
    if (node === null) return false;
    if (inorder(node.left)) return true;
    if (prev === p) {
      ans = node;
      return true;
    }
    prev = node;
    if (inorder(node.right)) return true;
    return false;
  }
}