- Difficulty: Medium
https://leetcode.com/problems/inorder-successor-in-bst/
*Inorder successor in bst: the 1st value great than current value
That node is the smallest node in
p' right branch, if not found can either be p's parent else null . 思路1： Find p in the tree, use a stack to store the path. 2 cases
1. if the right node is not empty，print the leftmost leaf of rightnode or itself.
2. if the right node is null, print the 1st value in stack that is greater than curr.val
else not found return null.
Complexity: time O(n) - store path. space O(n)
public class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { if(root == null)return root; Deque<TreeNode> st = new LinkedList<TreeNode>(); TreeNode curr = root; // Find the target node while saving the path while(curr!=p){ st.push(curr); if(curr.val > p.val){ curr = curr.left; }else{ curr = curr.right; } } // if curr has right node, find the leftmost of right node(or itself), is the successor if(curr.right != null){ curr = curr.right; while(curr.left != null){ curr = curr.left; } return curr; }else{ // if curr has no right node, find the 1st node in stack that val > curr.val while(!st.isEmpty()){ if(st.peek().val>curr.val)return st.pop(); st.pop(); } // 如果栈都pop空了还没有比目标节点大的，说没有更大的了 return null; } } }
思路2： use dfs
参考： https://discuss.leetcode.com/topic/25076/share-my-java-recursive-solution/13
关键字： recursionWhen the code runs into the else block, that means the current root is eitherp's parent or a node inp's right branch.If it'sp's parent node, there are two scenarios: 1.pdoesn't have right child, in this case, the recursion will eventually return null, sop's parent is the successor; 2.phas right child, then the recursion will return the smallest node in the right sub tree, and that will be the answer.If it'sp's right child, there are two scenarios: 1. the right child has left sub tree, eventually the smallest node from the left sub tree will be the answer; 2. the right child has no left sub tree, the recursion will return null, then the right child (root) is our answer.
Complexity : time O(logn); space O(logn) for stack,
public class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { if(root == null){ return root;} if(root.val<=p.val){//利用BST性质 TreeNode right = inorderSuccessor(root.right,p);//successor in the right subtree return right; }else{ TreeNode left = inorderSuccessor(root.left,p);//looking for p in the left subtree return left != null?left:root;//null case: when leftmost leaf } } }
Predecessor
public class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { if(root == null){ return root;} if(root.val>=p.val){//利用BST性质 TreeNode left = inorderSuccessor(root.left,p); return left; }else{ TreeNode right = inorderSuccessor(root.right,p);//右叶，打印中叶或root return right != null?right:root; } } }
