1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    TreeNode successor;
    TreeNode lastVisited;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        dfs(root, p);
        return successor;
    }
    
    private void dfs(TreeNode node, TreeNode target) {
        if (node == null)
            return;
        dfs(node.left, target);
        if (successor != null)
            return;
        if (lastVisited == target) {
            successor = node;
            return;
        }
        lastVisited = node;
        dfs(node.right, target);
    }
    
}

用一个全局变量来存最近visit的那个node是什么. 然后dfs遍历所有的node即可. 遇到某个node的上一个是target的, 就返回该node.

时间复杂度: O(n)
空间复杂度: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode currNode = root;
        TreeNode lastValidParent = null;
        while (currNode != p) {
            if (p.val < currNode.val) {
                lastValidParent = currNode;
                currNode = currNode.left;
            } else {
                currNode = currNode.right;
            }
        }
        if (currNode.right != null) {
            currNode = currNode.right;
            while (currNode.left != null) {
                currNode = currNode.left;
            }
            return currNode;
        }
        return lastValidParent;
    }
}

这个方法就是我们先根据BST的性质找到这个p. 如果p有右树, 那么successor就是右树最左边的那个node. 如果没有我们要开始从p原路向上走, 如果p是它的parent的左node, 那么它的parent就是答案. 如果是它的parent的右node, 这表明p的parent的代表的树遍历完毕, 我们需要继续向上, 再看p的parent是它的parent的哪个node, 如果是左node, 那么p的parent的parent就是答案, 如果是右node, 那么我们继续走, 以此类推.我们一直走要么就是遇到某个node是自己parent的左node, 然后此时该node的parent就是答案, 要么就是到达root的时候也没有遇到这种情况, 此时答案就是null.

由于我们没有parent这个指针. 因此我们用一个变量来记录我们找p的时候, 看哪个node作为了它的parent的左node, 我们记录这个parent, 只要遇到这样的parent我们就更新我们用来记录的变量来存最近遇到的满足我们要求的parent. 那么等到p往上回去找的时候, 一定会原路返回到达这个node, 此时该node是自己parent的左node, 因此这个parent就是答案. 这里需要注意的是只要在找的过程中遇到某个node是它parent的左node, 我们就更新我们的变量, 记录下这个parent, 因此等到最后找到p的时候, 我们记录的这个parent是距离p最近的(沿着找的路线回去的时候第一个会遇到的满足我们要求的parent).

时间复杂度: Average: O(logn) Worst: O(n) 可能是个链表.
空间复杂度: O(1)

我之前一直在尝试, 如何到达某个node知道它的前一个node是什么. 如果它有左树, 那么最后一个node就是左树最左边的那个.
如果没有, 那么就是一路向上, 直到到达某个node时, 是从该node的右侧回到该node的, 不能简单的认为如果该node不是自己parent的right
node, 这个node就没有prev了, 因为自己的parent可能还是它的parent的right node, 此时自己parent的parent就是prev node. 当然parent的
parent可能也不符合条件, 需要我们继续找, 直到找到root, 才能证明我们的prev是null. 因此某个node的prev node既可能在自己的上方,
又可能在自己的下方. 所以用一个global variable记录last visited node是比较好的方法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  class Solution {
    
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        while (root != null) {
            if (p.val >= root.val) {
                root = root.right;
            } else {
                successor = root;
                root = root.left;
            }
        }
        return successor;
    }
}

这个方法等于是把我们的方法二的两种情况结合了. 也就是遇到在某个node要左拐的时候, 我们就记录下这个node, 一直到我们找到p的时候, 我们记录的就是距离p最近的满足我们条件的parent. 此时如果我们还有右树, 那么我们就会右拐(p.val == root.val), 之后遇到的值肯定都大于p.val(因为是p的右树), 因此我们一直会左拐, 直到到达null. 此时记录的就是p右树最左边的node.

时间复杂度和空间复杂度不变.

以下网友分享的答案. 其实思路和方法三一样, 只不过是用递归实现.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public TreeNode successor(TreeNode root, TreeNode p) {
        if (root == null)
          return null;
      
        if (root.val <= p.val) {
          return successor(root.right, p);
        } else {
          TreeNode left = successor(root.left, p);
          return (left != null) ? left : root;
        }
    }
}

这个思路很巧妙. 如果p.val > root.val那么p在root.right所在的树中, p的successor也在root的右树中(如果有的话), 我们直接return helper(root.right, target). 如果p.val < root.val, p在左树中, 然后去看左树中有没有successor, 如果没有successor, 那么这个succcessor就是root. 如果p.val == root.val, 我们找到了p, 此时我们看右树有没有node, 因此继续调用helper(root.right, target). 如果它返回null, 就说明右树没有successor, 我们直接return即可.

后来的的思考

对于这个答案, 如果我们遇到的值小于p, 那么此时的node不可能是successor, 因为inorder是从小到大遍历, 我们肯定先被遍历, 于是successor只可能出现在此时node的右支里面, 如果node的值小于p, 那么此时的node可能是successor但不确定, 于是从左枝里面找一找, 如果能找到, 那就是找到的这个, 如果找不到, 那么就是此时的node. 如果node等于p, 那么我们从右支找一下最左边的node, 如果此时右支没东西, 那么会直接返回null, 这说明p的successor不在这里, 往上返回吧, 看上面有没有潜在的successor. 如果有右支, 我们是一路向左, 此时我们会一直进入root.val > p.val的情况, 也就是else的情况, 直到遇到null返回null, 此时上一层发现返回了null, 但是自己可能是successor(因为自己比p大), 那么就会返回自己, 再上一层发现下面找到了successor, 那就会帮忙返回这个successor, 以此类推, 最终就找到了.

只能说这个递归函数设计的原理就是只要往左拐, 也就是此时的node比p大, 我就记录一下先, 然后看左支有没有更好的答案, 如果有那就返回它, 没有就返回自己. 这个逻辑适合p的右支找最左边的node, 也适合从root出发去p的路上记录p的successor. 可以说非常巧妙了.

后来的感想II

这个递归函数的功能其实就是找一个树中, 比p的值大的node中, 最小的那个node. 这就是递归函数的作用. 找到就找到, 没找到就返回null. 这是精髓. 这样的话看这个递归函数也就明白了. 如果node大于p, 那么从左树中比p大的数中最小的, 没找到就是这node; 如果node小于p, 那么从右树找, 没找到就没找到, 找到了就返回这个找到的. 如果node和p相等, 那么就去找右树中比p大的数中最小的, 找到就找到, 没找到就算了. 因此node等于和小于p的情况处理的逻辑一样, 于是合并他俩. 这个是最终版本了.