LintCode 448. Inorder Successor in Binary Search Tree 原创Java参考解答

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在中序遍历中的下一个节点。

  1. 先检查root节点是否为null,若是则返回null。
  2. 根据二叉搜索树性质,如果p点有右子树,那么p点在中序遍历中的下一节点为p点右子树的最左边节点。这里可以建立一个找树的最左边节点的辅助函数。
  3. 同样根据二叉搜索树性质,如果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; 
    } 
}
 

相关题目

LintCode All in One 原创题目讲解汇总

发表评论

电子邮件地址不会被公开。 必填项已用*标注