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:

return node 2.

Given tree = [2,1,3] and node = 2:

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。

参考代码

相关题目

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

发表评论

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