0
189
VisualizaçõesTrying to solve Lowest common ancestor
var lowestCommonAncestor = function(root, p, q) {
// return the path to the node
let path = []
const search = (node, target) => {
if (node === null) return false
path.push(node)
if (node === target) return true
const leftSearched = search(node.left, target)
if (leftSearched) return true
const rightSearched = search(node.right,target)
if (rightSearched) return true
path.pop()
}
search(root, p)
const pathP = path
path = []
search(root, q)
const pathQ = path
let result
while(pathP.length > 0 && pathQ.length > 0 && pathP[0] === pathQ[0]) {
result = pathP[0]
pathP.shift()
pathQ.shift()
}
return result
};
console.log(lowestCommonAncestor([3,5,1,6,2,0,8,null,null,7,4],5,1));
Iam getting following error message const leftSearched = search(node.left, target) ^ TypeError: Cannot read property 'left' of undefined
Could someone help me to fix this issue
·
Juan Pablo Isaza
1 Respostas
Responde à pergunta0
Leet Code, as some other code challenge sites, will transform the array input (actually the text input having JSON notation) into an instance of TreeNode, and will pass that as argument to the function with your solution code.
When you want to run the solution locally, you'll have to take care of this transformation yourself. For that purpose you could make use of the fromList function -- specifically for binary trees.
NB: you have a bug in your search function. if (node === target) should be if (node.val === target).
// LeetCode template:
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
// Tool to convert array input to a tree:
function fromList(values) {
if (!values) return;
let it = (function* () {
for (let value of values) {
yield value == null ? null : new TreeNode(value);
}
while (true) yield null;
})();
let root = it.next().value;
let nextlevel = [root];
while (nextlevel.length) {
let level = nextlevel;
nextlevel = [];
for (let node of level) {
if (node) {
node.left = it.next().value;
node.right = it.next().value;
nextlevel.push(node.left, node.right);
}
}
}
return root;
}
// Your function
var lowestCommonAncestor = function(root, p, q) {
// return the path to the node
let path = []
const search = (node, target) => {
if (node === null) return false;
path.push(node);
if (node.val === target) return true;
const leftSearched = search(node.left, target);
if (leftSearched) return true;
const rightSearched = search(node.right,target);
if (rightSearched) return true;
path.pop();
}
search(root, p);
const pathP = path;
path = [];
search(root, q);
const pathQ = path;
let result;
while(pathP.length > 0 && pathQ.length > 0 && pathP[0] === pathQ[0]) {
result = pathP[0];
pathP.shift();
pathQ.shift();
}
return result;
};
// Running your solution on some input
let input = [3,5,1,6,2,0,8,null,null,7,4];
// Make the conversion that LeetCode would do
let root = fromList(input);
let lca = lowestCommonAncestor(root,5,1);
// For your own purposes, just print the value of that node:
console.log(lca.val); // 3
·
Juan Pablo Isaza
Relatório
Responde à pergunta