经典算法实例应用：后继者

我们先来看题目描述设计一个算法找出二叉搜索树中指定节点的“下一个”节点也即中序后继。如果指定节点没有对应的“下一个”节点则返回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解决方案方法一中序遍历思路和算法为了找到二叉搜索树中的节点 p 的后继节点最直观的方法是中序遍历。由于只需要找到节点 p 的后继节点因此不需要维护完整的中序遍历序列只需要在中序遍历的过程中维护上一个访问的节点和当前访问的节点。如果上一个访问的节点是节点 p 则当前访问的节点即为节点 p 的后继节点。如果节点 p 是最后被访问的节点则不存在节点 p 的后继节点返回 null 。代码Python3class 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 NoneJavaclass Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { DequeTreeNode stack new ArrayDequeTreeNode(); TreeNode prev null, curr root; while (!stack.isEmpty() || curr ! null) { while (curr ! null) { stack.push(curr); curr curr.left; } curr stack.pop(); if (prev p) { return curr; } prev curr; curr curr.right; } return null; } }C#public class Solution { public TreeNode InorderSuccessor(TreeNode root, TreeNode p) { StackTreeNode stack new StackTreeNode(); TreeNode prev null, curr root; while (stack.Count 0 || curr ! null) { while (curr ! null) { stack.Push(curr); curr curr.left; } curr stack.Pop(); if (prev p) { return curr; } prev curr; curr curr.right; } return null; } }​Cclass Solution { public: TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { stackTreeNode* st; TreeNode *prev nullptr, *curr root; while (!st.empty() || curr ! nullptr) { while (curr ! nullptr) { st.emplace(curr); curr curr-left; } curr st.top(); st.pop(); if (prev p) { return curr; } prev curr; curr curr-right; } return nullptr; } };复杂度分析时间复杂度O(n) 其中 n 是二叉搜索树的节点数。中序遍历最多需要访问二叉搜索树中的每个节点一次。空间复杂度O(n) 其中 n 是二叉搜索树的节点数。空间复杂度取决于栈深度平均情况是 O(logn) 最坏情况是 O(n) 。