Lstmxx的空间

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

链接

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  let res = null
  if (root === null) return res
  const nodeQues = []
  nodeQues.push(root)
  let pNode = null
  let qNode = null
  while(nodeQues.length > 0) {
    const childNodes = nodeQues.splice(0)
    const childLen = childNodes.length
    if (pNode !== null && qNode !== null) break
    for(let i = 0; i < childLen;i++) {
      const node = childNodes[i]
      if (node) {
        if (node.val === p.val) {
          pNode = node
        } else if (node.val === q.val) {
          qNode = node
        }
        if (pNode !== null && qNode !== null) break
        if (node.left) {
          node.left.parent = node
          nodeQues.push(node.left)
        }
        if (node.right) {
          node.right.parent = node
          nodeQues.push(node.right)
        }
      }
    }
  }
  if (pNode === null || qNode === null || pNode.val === qNode.val) {
    return pNode ? pNode.val : qNode.val
  }
  const pNodeMap = {}
  while(pNode) {
    pNodeMap[pNode.val] = true
    pNode = pNode.parent
  }
  while(qNode) {
    if (pNodeMap[qNode.val]) {
      res = qNode
      console.log(pNodeMap[qNode.val], res)
      break
    }
    qNode = qNode.parent
  }
  return res
}