LeetCode 510. Inorder Successor in BST II

浅浅的花香味﹌ 2021-11-13 15:34 190阅读 0赞

原题链接在这里：[https://leetcode.com/problems/inorder-successor-in-bst-ii/][https_leetcode.com_problems_inorder-successor-in-bst-ii]

题目：

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

The successor of a node `p` is the node with the smallest key greater than `p.val`.

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node.

Example 1:

![285_example_1.PNG][]

Input: 
    root = {"$id":"1","left":{"$id":"2","left":null,"parent":{"$ref":"1"},"right":null,"val":1},"parent":null,"right":{"$id":"3","left":null,"parent":{"$ref":"1"},"right":null,"val":3},"val":2}
    p = 1
    Output: 2
    Explanation: 1's in-order successor node is 2. Note that both p and the return value is of Node type.

Example 2:

![285_example_2.PNG][]

Input: 
    root = {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":1},"parent":{"$ref":"2"},"right":null,"val":2},"parent":{"$ref":"1"},"right":{"$id":"5","left":null,"parent":{"$ref":"2"},"right":null,"val":4},"val":3},"parent":null,"right":{"$id":"6","left":null,"parent":{"$ref":"1"},"right":null,"val":6},"val":5}
    p = 6
    Output: null
    Explanation: There is no in-order successor of the current node, so the answer is null.

Example 3:

![285_example_34.PNG][]

Input: 
    root = {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":2},"parent":{"$ref":"2"},"right":{"$id":"5","left":null,"parent":{"$ref":"3"},"right":null,"val":4},"val":3},"parent":{"$ref":"1"},"right":{"$id":"6","left":null,"parent":{"$ref":"2"},"right":{"$id":"7","left":{"$id":"8","left":null,"parent":{"$ref":"7"},"right":null,"val":9},"parent":{"$ref":"6"},"right":null,"val":13},"val":7},"val":6},"parent":null,"right":{"$id":"9","left":{"$id":"10","left":null,"parent":{"$ref":"9"},"right":null,"val":17},"parent":{"$ref":"1"},"right":{"$id":"11","left":null,"parent":{"$ref":"9"},"right":null,"val":20},"val":18},"val":15}
    p = 15
    Output: 17

Example 4:

![285_example_34.PNG][]

Note:

1.  If the given node has no in-order successor in the tree, return `null`.
2.  It's guaranteed that the values of the tree are unique.
3.  Remember that we are using the `Node` type instead of `TreeNode` type so their string representation are different.

Follow up:

Could you solve it without looking up any of the node's values?

题解：

Successor could exist in 2 possible positions.

If x has right child, successor must be below its right child, x.right, then keep going down left.

Otherwise, successor could be x going up untill hitting first ancestor through left edge. There may be case that it keeps going up through right edge, then there is no successor.

Time Complexity: O(h). h is the height of tree.

Space: O(1).

AC Java:

1 /*
     2 // Definition for a Node.
     3 class Node {
     4     public int val;
     5     public Node left;
     6     public Node right;
     7     public Node parent;
     8 };
     9 */
    10 class Solution {
    11     public Node inorderSuccessor(Node x) {
    12         if(x == null){
    13             return x;
    14         }
    15         
    16         if(x.right != null){
    17             Node suc = x.right;
    18             while(suc.left != null){
    19                 suc = suc.left;
    20             }
    21             
    22             return suc;
    23         }
    24         
    25         while(x.parent != null && x.parent.right == x){
    26             x = x.parent;
    27         }
    28         
    29         return x.parent;
    30     }
    31 }

转载于:https://www.cnblogs.com/Dylan-Java-NYC/p/11015316.html

[https_leetcode.com_problems_inorder-successor-in-bst-ii]: https://leetcode.com/problems/inorder-successor-in-bst-ii/
[285_example_1.PNG]: https://assets.leetcode.com/uploads/2019/01/23/285_example_1.PNG
[285_example_2.PNG]: https://assets.leetcode.com/uploads/2019/01/23/285_example_2.PNG
[285_example_34.PNG]: https://assets.leetcode.com/uploads/2019/02/02/285_example_34.PNG