试图解决最低共同祖先

Question

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));

我收到以下错误消息 const leftSearched = search(node.left, 目标) ^ 类型错误：无法读取未定义的属性 'left'

谁能帮我解决这个问题

Answer 1

Leet Code 和其他一些代码挑战网站一样，会将数组输入（实际上是具有 JSON 符号的 text 输入）转换为 TreeNode，并将 that 作为参数传递给带有您的解决方案代码的函数。

当您想运行本地解决方案时，您必须自己处理此转换。为此，您可以使用 fromList 函数——专门用于二叉树。

注意：您的 search 函数中存在错误。 if (node === target) 应该是 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

试图解决最低共同祖先

Trying to solve Lowest common ancestor

javascript

binary-search-tree