Inorder Successor in Binary Search Tree

本文主要是介绍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.

使用中序遍历的方式进行求解

java

public class Solution {public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {if (root == null || p == null) {return null;}List<TreeNode> path = inOrder(root);int index = path.indexOf(p);return index == -1 || index == path.size() - 1 ? null : path.get(index + 1);}private List<TreeNode> inOrder(TreeNode root) {List<TreeNode> result = new ArrayList<>();if (root == null) {return result;}List<TreeNode> left = inOrder(root.left);List<TreeNode> right = inOrder(root.right);result.addAll(left);result.add(root);result.addAll(right);return result;}
}

使用二叉树的性质进行求解

public class Solution {public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {if (root == null || p == null) {return null;}if (root.val <= p.val) {return inorderSuccessor(root.right, p);} else {TreeNode left = inorderSuccessor(root.left, p);return left == null ? root : left;}}
}

这篇关于Inorder Successor in Binary Search Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---