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

链接：236.二叉树的最近公共祖先
难度：Medium
标签：树、深度优先搜索、二叉树
简介：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

题解 1 - javascript

• 编辑时间：2020-05-10
• 执行用时：84ms
• 内存消耗：42.5MB
• 编程语言：javascript
• 解法介绍：通过 js 特性给每个节点添加 parent 属性，遍历是否有相同父节点进行判断。

/**
 * 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) {
  function treeNodeInorder(node) {
    if (node.left !== null) {
      node.left.parent = node;
      treeNodeInorder(node.left);
    }
    if (node.right !== null) {
      node.right.parent = node;
      treeNodeInorder(node.right);
    }
  }
  treeNodeInorder(root);
  root.parent = root;
  let temp = p;
  const queueP = [temp];
  while (temp.parent !== root) {
    queueP.push(temp.parent);
    temp = temp.parent;
  }
  queueP.push(root);
  temp = q;
  const queueQ = [temp];
  while (temp.parent !== root) {
    queueQ.push(temp.parent);
    temp = temp.parent;
  }
  queueQ.push(root);
  for (const node of queueP) {
    if (queueQ.includes(node)) return node;
  }
  return root;
};

题解 2 - python

• 编辑时间：2024-02-09
• 执行用时：56ms
• 内存消耗：21.32MB
• 编程语言：python
• 解法介绍：遍历记录父亲和level。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        map = {}
        plevel = qlevel = 0
        def dfs(node: Optional[TreeNode], level = 0):
            nonlocal plevel, qlevel
            if not node: return
            if node == p: plevel = level
            if node == q: qlevel = level
            if node.left:
                map[node.left] = node
                dfs(node.left, level + 1)
            if node.right:
                map[node.right] = node
                dfs(node.right, level + 1)
        dfs(root)
        if plevel > qlevel:
            plevel, qlevel = qlevel, plevel
            p, q = q, p
        while qlevel > plevel:
            print(q, qlevel)
            qlevel -= 1
            q = map[q]
        while p != q:
            p, q = map[p], map[q]
        return p