Problem: 面試題 04.06. 后繼者

題目描述

設計一個算法，找出二叉搜索樹中指定節點的“下一個”節點（也即中序后繼）。

如果指定節點沒有對應的“下一個”節點，則返回null。

思路

由于題意是找出一個在二叉搜索樹中給定的節點的后繼節點，按示例意思可知道為求二叉搜索樹中序遍歷遞增序列中給定一個節點的相鄰的下一個更大的值，進一步分析可得為利用二叉搜索樹中序遍歷的得出遞增序列，再在此基礎上求取一給定值的下一個比給定值大的值

解題方法

1.定義兩個成員變量，一個用于記錄在中序遍歷過程中，當前節點是否為指定節點（假設為comming 返回類型為boolean），一個用于返回最后的結果（假設為succession 返回類型為TreeNode）（由于本解法用到遞歸處理二叉樹的中序遍歷，所以定義兩個成員變量用于輔助記錄！）
2.中序遍歷查找指定節點，若當前節點是指定節點，則將comming修改為true，當再在遞歸過程中判斷comming為true時則表示當前節點為指定節點的下一個節點，將當前節點指向succession，最后返回即可。
3.注意：在遞歸過程中若判斷succession不為null時說明已經找到后繼節點，則可以提前結束遞歸！！！

復雜度

• 時間復雜度:

$O(n)$

• 空間復雜度:

$O(n)$

Code

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {//Time Complexity: O(n)//Space Complexity: O(n)//用與記錄下一個private boolean comming = false;private TreeNode successor = null;public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {inOrder(root,p);return successor;}private void inOrder(TreeNode root, TreeNode p) {if (root == null) {return;}inOrder(root.left,p);if (successor != null) {return;}//如果上一個節點是指定節點if (comming == true) {successor = root;comming = false;}//入果當前節點是指點節點//將comming設置為trueif (root == p) {comming = true;}inOrder(root.right,p);}
}