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

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

这个题，我的思路是先遍历整棵树，给每个节点建立parent，同时找到pq两个节点

然后把p q两个节点的所有祖先存储到数组

从后向前遍历这两个数组，找到分叉的节点

/**
 * 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 pNode = null;
    let qNode = null;

    const travel = (root, parent) => {
        root.parent = parent;
        if (root.val === p) {
            pNode = root;
        }
        if (root.val === q) {
            qNode = root;
        }
        root.left && travel(root.left, root);
        root.right && travel(root.right, root);
    };

    travel(root, null);

    const ps = [];
    const qs = [];

    while (pNode) {
        ps.push(pNode);
        pNode = pNode.parent;
    }
    while (qNode) {
        qs.push(qNode);
        qNode = qNode.parent;
    }

    console.log(ps.map(i => i.val), qs.map(i => i.val));
    let n = root;
    while (ps.length > 0 && qs.length > 0) {
        p = ps.pop();
        q = qs.pop();

        if (p !== q) {
            break;
        } else {
            n = p;
        }
    }
    return n;
};

const tree = {
    val: 3,
    left: {
        val: 5,
        left: {
            val: 6
        },
        right: {
            val: 2,
            left: {
                val: 7
            },
            right: {
                val: 4
            }
        }
    },
    right: {
        val: 1,
        left: {
            val: 0
        },
        right: {
            val: 8
        }
    }
};

console.log(lowestCommonAncestor(tree, 5, 1));
console.log(lowestCommonAncestor(tree, 5, 4));