- Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
- Note: If the given node has no in-order successor in the tree, return null.
给一个二叉搜索树和它的一个节点, 找出它的中序后继节点, 如果没有返回 null
解法 1: 用中序遍历二叉搜索树, 当找到 root.val = p.val 的时候, 返回下一个节点 T: O(n), S: O(n)
解法 2: 利用 BST 的性质, 不用遍历全部元素比较 root.val 和 p.val, 然后在左子树或者右子树中查找 T: O(h), S: O(1)
如果节点 p 有右子树, 那么 p 的后继节点为右子树的的最左值 (即最后一个没有左子树的节点);
如果节点 p 没有右子树, 就在二叉搜索树中搜索节点 p, 并在从上往下的查找过程中依次更新记录比 p 的 val 值大的节点
- Java:
- /**
- * 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;
- }
- boolean foundNodeP = false;
- Stack<TreeNode> stack = new Stack<>();
- while(root != null || !stack.isEmpty()) {
- if(root != null) {
- stack.push(root);
- root = root.left;
- } else {
- root = stack.pop();
- if(foundNodeP) {
- return root;
- }
- if(root.val == p.val) {
- foundNodeP = true;
- }
- root = root.right;
- }
- }
- return null;
- }
- }
- Java:
- public class Solution {
- public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
- if(root == null || p == null) {
- return null;
- }
- TreeNode successor = null;
- while(root != null) {
- if(p.val <root.val) {
- successor = root;
- root = root.left;
- } else {
- root = root.right;
- }
- }
- return successor;
- }
- }
- Java:
- public class Solution {
- public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
- TreeNode node = root,
- successor = null;
- while (node != null) {
- if (node.val> p.val) {
- successor = node;
- node = node.left;
- } else {
- node = node.right;
- }
- }
- return successor;
- }
- }
- Python:
- class Solution(object):
- def inorderSuccessor(self, root, p):
- """
- :type root: TreeNode
- :type p: TreeNode
- :rtype: TreeNode
- """
- # If it has right subtree.
- if p and p.right:
- p = p.right
- while p.left:
- p = p.left
- return p
- # Search from root.
- successor = None
- while root and root != p:
- if root.val> p.val:
- successor = root
- root = root.left
- else:
- root = root.right
- return successor
- C++:
- class Solution {
- public:
- TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
- TreeNode *res = NULL;
- while (root) {
- if (root->val> p->val) {
- res = root;
- root = root->left;
- } else root = root->right;
- }
- return res;
- }
- };
- C++: Recursion
- class Solution {
- public:
- TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
- if (!root) return NULL;
- if (root->val <= p->val) {
- return inorderSuccessor(root->right, p);
- } else {
- TreeNode *left = inorderSuccessor(root->left, p);
- return left ? left : root;
- }
- }
- };
类似题目:
[LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历
[LeetCode] 173. Binary Search Tree Iterator 二叉搜索树迭代器
来源: http://www.bubuko.com/infodetail-2541141.html