Shinkai005
V1
2022/05/19阅读:15主题:红绯
【leetcode】面试题 04.06. 后继者
【leetcode】面试题 04.06. 后继者
题目描述
个人题解及思路t(n)s(n)
就是简单中序遍历,找到那个节点就停止,但是肯定不能找到就停----毕竟要取下一个
因此循环到下一个,然后对比pre===p,即可.
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @return {TreeNode}
*/
var inorderSuccessor = function(root, p) {
const stack = [];
let pre = null, cur = root;
while (stack.length || cur) {
while (cur) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (pre === p) {
return cur;
}
pre = cur;
cur = cur.right;
}
return null;
};
这个不是我的题解,是官方的,我用的递归版本,这块我不知道是js的问题还是题目问题.我传进arr里比较就无法比较,拿出来才可以比较.
官方的写法是直接不存数组,毕竟官方没要求存,只需要单个的节点的下一个.
“还是太年轻了,一定要精简数据结构.下面我改出来递归版本.
”
其他题解
var inorderSuccessor = function(root, p) {
const res = []
let pos = 0
let index = 0
const dfs = (root) => {
if(!root) return
dfs(root.left)
res.push(root)
if(root === p){
pos = index
}
index++
dfs(root.right)
}
dfs(root)
return res[pos+1] || null
};
“这个版本好的点在不用再遍历一次,因为二叉搜索树会按顺序走,所以找到当前节点,然后再+1就是下一位了.
但是这个弊端要遍历完.
”
容易理解的版本
var inorderSuccessor = function(root, p) {
const arr = [];
const dfs = (node) => {
if(node === null) {
return;
}
dfs(node.left);
arr.push(node);
dfs(node.right);
}
dfs(root);
for(var i=0;i<arr.length;i++) {
if(arr[i] === p) {
return arr[i+1] ? arr[i+1] : null;
}
}
};
“大多数人会这么写,但是后面的for循环就没意义了,因为本身二叉搜索树是顺序的.
”
总结优化
实在没想出来,怎么在递归版本找到root之后再找一层就不找了.sorry能力有限
作者介绍
Shinkai005
V1
公众号:深海笔记Shinkai