目录

1. 问题描述

2. 思路与算法

3. 代码实现

1. 问题描述

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例 1:

输入: root = [2,1,3], p = 1
  2
 / \
1   3

输出: 2

示例 2:

输入: root = [5,3,6,2,4,null,null,1], p = 6
      5
     / \
    3   6
   / \
  2   4
 /   
1

输出: null

2. 思路与算法

        直接进行中序遍历。

        由于只需要找到节点 p 的后继节点，因此不需要维护完整的中序遍历序列，只需要在中序遍历的过程中维护上一个访问的节点和当前访问的节点。如果上一个访问的节点是节点 p，则当前访问的节点即为节点 p 的后继节点。

        如果节点 p 是最后被访问的节点，则不存在节点 p 的后继节点，返回 。

        中序遍历可以用深度优先搜索按照（1）左子树；(2) 根节点；(3) 右子树，的顺序进行遍历。可以用递归的方式实现，也可以以显式地维护一个栈的方式来实现。

3. 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:

        st, pre, cur = [], None, root
        while st or cur:
            while cur:
                st.append(cur)
                cur = cur.left
            cur = st.pop()
            if pre == p:
                return cur
            pre = cur
            cur = cur.right
        return None

        回到总目录：Leetcode每日一题总目录(动态更新。。。)