一、暴力(中序)
使用二叉搜索树中序遍历有序的特性,对二叉树进行中序遍历存入集合当中,然后在末尾加入一个null(末尾节点的下一个为null)
得到题目中给定节点在集合中的下一位即可
二、BST 特性 + 递归
利用 BST 的特性,我们可以根据当前节点 root 与 p 的值大小关系来确定搜索方向:
- 若有
root.val <= p.val
: 根据 BST 特性可知当前节点 root 及其左子树子节点均满足 值小于等于 p.val ,因此不可能是 p 点的后继,抛弃到左子树,我们直接到 root 的右子树搜索 p 的后继(递归处理); - 若有
root.val > p.val
: 当第一次搜索到满足此条件的节点时,在以 root 为根节点的子树中 位于最左下方 的值为 p 的后继,但也有可能 root 没有左子树(为空),因此 p 的后继要么在 root 的左子树中(若有),要么是 root 本身,此时我们可以直接到 root 的左子树搜索,若搜索结果为空返回 root 然后逐层返回,否则返回逐层返回搜索结果。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (root == null || p == null) {
return null;
}
//p节点的值比当前节点的值大或者相等,说明p节点的后继不可能在当前节点的左子树上(因为中序遍历的左子树的值比当前节点的值小)
//要设法去当前节点的右子树上找
if (root.val <= p.val) {
return inorderSuccessor(root.right, p);
} else {
//p节点的值比当前节点小了
//case1 left为null,说明在左子树上没找到,此时返回当前节点root
//case2 left不为null,说明找到了返回left
TreeNode left = inorderSuccessor(root.left, p);
return left == null ? root : left;
}
// 暴力
// List list = new ArrayList<>();
// public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
// if(root == null) {return null;}
// inorder(root);
// list.add(null);
// return list.get(list.indexOf(p) + 1);
// }
// public void inorder(TreeNode root) {
// if(root == null) {
// return;
// }
// inorder(root.left);
// list.add(root);
// inorder(root.right);
// }
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)