设计一个算法,找出二叉搜索树中指定节点的“下一个”节点(也即中序后继)。
如果指定节点没有对应的“下一个”节点,则返回null。
示例 1:
输入: root = [2,1,3], p = 1
2
/ \
1 3
输出: 2
示例 2:
输入: root = [5,3,6,2,4,null,null,1], p = 6
5
/ \
3 6
/ \
2 4
/
1
输出: null
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/successor-lcci
对于此题,我们首先得先知道先序、中序、后序遍历。
(很难受,图片在简书上下载是webp格式,上传居然不支持,我特么服!老子手动截图!)
二叉树.png
前序
先访问根节点,即父节点,再访问当前节点的左子树,若当前节点无左子树,则访问右子树;
上图前序遍历结果:1,2,4,5,3,6,7
中序
先访问当前节点的左子树,再访问当前节点的父节点,若当前节点无左子树,则访问当前节点的右子树
上图中序遍历结果:4,2,5,1,6,3,7
后序
先访问当前节点的左子树,若当前节点无左子树,则访问当前节点的右子树,最后访问当前节点的父节点
上图后序遍历结果:4,5,2,6,7,3,1
这些看明白了,那么就看上面的示例,拿[5,3,6,2,4,null,null,1]来举例,
5的左右子节点是3,6
3的左右节点是2,4
6的左右节点是null,null
2只有左节点1
按照中序来操作,要确定某个节点的下一个节点,这个也不是那么好操作。
但换个角度来思考,我们判断某个节点的前一个节点是否符合目标,是不是更方便操作。
那么实现代码如下(先声明这段js代码执行上面示例会有问题的,因为力扣网对树、图、链等题是有封装方法的,只需要我们去实现代码逻辑):
var inorderSuccessor = function(root, p) {
let tree = root,arr = [],res;
while(arr.length || tree){
while(tree){
arr.push(tree);
tree = tree.left;
}
tree = arr.pop();
if(res == p){
return tree;
}
res = tree;
tree = tree.right;
}
return null;
};