My code:
/**
* 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) {
if (root == null || p == null) {
return null;
}
if (p.right != null) {
TreeNode ret = p.right;
while (ret.left != null) {
ret = ret.left;
}
return ret;
}
TreeNode pre = null;
TreeNode curr = root;
while (curr != null) {
if (curr.left == p) {
return curr;
}
else if (curr.right == p) {
return pre;
}
else if (curr.val < p.val) {
curr = curr.right;
}
else {
pre = curr;
curr = curr.left;
}
}
return null;
}
}
首先，这道题目我竟然从来没做过，我表示很好奇。在我脑海里，我好像做过好几次了。最终导致我不能一边AC
我自己写出了这个iteration 的做法。
然后关键点在哪里呢？
在于，当 curr.val < p.val的时候，
curr = curr.right, 但我们不用更新pre
也就是说，当curr往右边走的时候，
pre指针保留在原地。这是为了防止，p是 curr这个subtree的最右边的结点，那么他的继承者就是pre，所以pre不能动。
或者可以这么说，如果curr往右走，那么p的继承者不一定会出现在这课右子树上，所以pre得做好准备
如果往左走，那么p的继承者，一定在这棵左子树上！pre可以跟进
如果curr往左边走，那么就可以更新curr了。
如果p是curr的左孩子，那么curr就是继承者。
如果p是curr的右孩子，那么pre就是继承者
同时，一开始，就先判断 p的右孩子是否为空。
如果不是，那么他的继承者，一定是右子树的最左边结点。
这就是 iteration 做法的思考点
然后看答案看到了recursion做法，感觉很巧妙，自己写了下。
My code:
/**
* 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) {
if (root == null) {
return null;
}
if (root.val <= p.val) {
return inorderSuccessor(root.right, p);
}
else {
TreeNode left = inorderSuccessor(root.left, p);
return left == null ? root : left;
}
}
}
巧妙在，他的分割点选的很好。
为什么一定是 root.val <= p.val 作为第一个判断条件呢？
因为 root.val <= p.val, 那么 p 的继承者一定在右子树
如果 root.val >= p.val, p的继承者不一定就在左子树！
所以这个地方如此写是用了很多心的。
接着往下看。
但我们走到 root.val > p.val的时候，
这个时候我们需要往左走。这个时候，继承者可能存在于左子树上，也可能是当前这个结点。所以加了一层判断。
这里的root，其实就相当于iteration里面的pre指针。
每当pre指针需要往左走的时候，都得考虑下。
如果curr是往右走，那么pre不用往走左。
如果curr往左走，这个时候pre才用往左走。
下面考虑下求 Predecessor 问题。
My code:
public class Solution {
public TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
if (root == null) {
return null;
}
else if (root.left != null) {
TreeNode ret = root.left;
while (ret.right != null) {
ret = ret.right;
}
return ret;
}
TreeNode curr = root;
TreeNode pre = null;
while (curr != null) {
if (curr.left == p) {
return pre;
}
else if (curr.right == p) {
return curr;
}
else if (curr.val > p.val) {
curr = curr.left;
}
else {
pre = curr;
curr = curr.right;
}
}
return null;
}
}
和find继承者差不多，只不过完全相反。
recursion:
My code:
public class Solution {
public TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
if (root == null) {
return null;
}
if (root.val >= p.val) {
return inorderPredecessor(root.left, p);
}
else {
TreeNode right = inorderPredecessor(root.right, p);
return right == null ? root : right;
}
}
}
也差不多。只是相反。
reference：
https://discuss.leetcode.com/topic/25076/share-my-java-recursive-solution/2
估计过段时间就忘记了。但希望能记住这个思想，那么临场就能很快地写出来。
Anyway, Good luck, Richardo! -- 09/06/2016
My code:
/**
* 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) {
TreeNode pre = null;
TreeNode curr = root;
while (curr != null) {
if (curr.val > p.val) {
pre = curr;
curr = curr.left;
}
else if (curr.val < p.val) {
curr = curr.right;
}
else {
if (curr.right != null) {
curr = curr.right;
while (curr.left != null) {
curr = curr.left;
}
return curr;
}
else {
return pre;
}
}
}
return null;
}
public TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
TreeNode curr = root;
TreeNode pre = null;
while (curr != null) {
if (curr.val < p.val) {
curr = curr.left;
}
else if (curr.val > p.val) {
pre = curr;
curr = curr.right;
}
else {
if (curr.left != null) {
curr = curr.left;
while (curr.right != null) {
curr = curr.right;
}
return curr;
}
else {
return pre;
}
}
}
return null;
}
}
正好完全相反
Anyway, Good luck, Richardo! -- 09/25/2016
