LintCode 448. Inorder Successor in Binary Search Tree 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/inorder-successor-in-binary-search-tree/
Given a binary search tree (See Definition) and a node in it, find the in-order successor of that node in the BST.
If the given node has no in-order successor in the tree, return null.
Notice
It’s guaranteed p is one node in the given tree. (You can directly compare the memory address to find p)
Example
Given tree = [2,1] and node = 1:
2
/
1
return node 2.
Given tree = [2,1,3] and node = 2:
2
/ \
1 3
return node 3.
解题思路
题目是求一个在二叉搜索树上的节点p在中序遍历中的下一个节点。
- 先检查root节点是否为null，若是则返回null。
- 根据二叉搜索树性质，如果p点有右子树，那么p点在中序遍历中的下一节点为p点右子树的最左边节点。这里可以建立一个找树的最左边节点的辅助函数。
- 同样根据二叉搜索树性质，如果p点没有右子树。那么由root出发，根据比较root和p点的大小关系，让root逐渐成为p点。设successor初始为null，在root向下移动过程中不断更新successor。最后返回root变为p点时候的successor。
参考代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
// write your code here
if (root == null) {
return null;
}
if (p.right != null) {
return leftMostOfTheTree(p.right);
} else {
TreeNode successor = null;
while (root != p) {
if (root.val > p.val) {
successor = root;
root = root.left;
} else {
root = root.right;
}
}
return successor;
}
}
private TreeNode leftMostOfTheTree(TreeNode root) {
while (root.left != null) {
root = root.left;
}
return root;
}
}