Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

找到兩個(gè)節(jié)點(diǎn)的最近公共祖先，思想是找到這兩個(gè)節(jié)點(diǎn)并找到這兩個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑，從下往上找到第一個(gè)相同的節(jié)點(diǎn)。
首先我想到的是使用遞歸找到這兩個(gè)節(jié)點(diǎn)，并將路徑保存在一個(gè)數(shù)組中，但是這樣在遞歸的過(guò)程中會(huì)用掉太多的內(nèi)存：

var lowestCommonAncestor = function(root, p, q) {
    var paths = [];
    var find = function(root, node, path) {
        if (root===null) {
            return 1;
        }
        path.push(root);
        if (root===node) {
            paths.push(path);
            return 1;
        }
        
        find(root.left,node,path.concat());
        find(root.right,node,path.concat());
        return 1;
    };
    find(root,p,[]);
    find(root,q,[]);
    console.log(paths)
    var n1 = paths[0].length;
    var n2 = paths[1].length;
    if (n1!==0&&n2!==0) {
        for (let i = n1 - 1;i >= 0;i--) {
            for (let j = n2 - 1;j >= 0;j--) {
                if (paths[0][i]===paths[1][j])
                    return paths[0][j];
            }
        }
    }
    return null;
};

這主要是因?yàn)橛刑嗟膒ath保存了太多冗余的信息。
換一種思路，我們使用一個(gè)map來(lái)保存每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，這樣我們?cè)谡业竭@兩個(gè)節(jié)點(diǎn)的時(shí)候可以通過(guò)map生成這兩個(gè)節(jié)點(diǎn)的路徑，所以這個(gè)map中最多保存n個(gè)節(jié)點(diǎn)的數(shù)據(jù)。
然后使用傳統(tǒng)的遍歷方法找這兩個(gè)節(jié)點(diǎn)就好了

var lowestCommonAncestor = function(root, p, q) {
    if (!root) 
        return null;
    var parent = new Map();
    var stack = [];
    parent[root.val] = undefined;
    stack.push(root);
    while ((parent.get(p) ===undefined || parent.get(q)===undefined) && stack.length!==0) {
        var node = stack.pop();
        if (node.left !== null) {
            parent.set(node.left,node);
            stack.push(node.left);
        }
        if (node.right !== null) {
            parent.set(node.right,node);
            stack.push(node.right);
        }
    }
    var ancestors = [];
    while (p !== undefined) {
        ancestors.push(p);
        p = parent.get(p);
    }
    while (q !== undefined) {
        for (var i = 0;i < ancestors.length;i++ ) {
            if (q===ancestors[i])
                return q;
        }
        q = parent.get(q);
    }     
};