一、問題描述
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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

image.png

二、解決思路
思路一：給定兩節(jié)點(diǎn)p、q，要找到其公共父節(jié)點(diǎn)，通過枚舉一些示例可以發(fā)現(xiàn)，pq兩節(jié)點(diǎn)之間的關(guān)系無非是父子關(guān)系和擁有共同父節(jié)點(diǎn)，若是父子關(guān)系，則父節(jié)點(diǎn)是所要求的節(jié)點(diǎn)，若擁有共同父節(jié)點(diǎn)，公共父節(jié)點(diǎn)是所要求的節(jié)點(diǎn)，因此可以采用遞歸來解決，遞歸結(jié)束條件為當(dāng)前節(jié)點(diǎn)為null
思路二：思路一采用遞歸，可以采用非遞歸思路來解決，要采用非遞歸的話，可以保存pq兩節(jié)點(diǎn)的所有父節(jié)點(diǎn)，最后求出所要求的節(jié)點(diǎn)

三、算法實(shí)現(xiàn)
思路一

private TreeNode node;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        //if(root.left == null || root.right == null) return root;
        checkCommonAncestor(root, p, q);
        return this.node;
    }

    public boolean checkCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return false;
        }
        boolean left = checkCommonAncestor(root.left, p, q);
        boolean right = checkCommonAncestor(root.right, p, q);
        boolean cur = (root == p || root == q);
        // pq位于root的左右兩邊
        if(left && right){
            this.node = root;
        }
        // pq中一節(jié)點(diǎn)為root節(jié)點(diǎn)
        if(cur && (left || right)){
            this.node = root;
        }
        return (left || right || cur);
    }

思路二

public boolean isNode(TreeNode root, TreeNode p, List<TreeNode> list){
        if(root == null){
            return false;
        }
        if(root == p){
            list.add(root);
            return true;
        } else{
            boolean left = isNode(root.left, p, list);
            boolean right = isNode(root.right, p, list);
            if(left || right) {
                list.add(root);
                return true;
            } else {
                return false;
            }
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        List<TreeNode> list = new ArrayList<>();
        isNode(root, p, list);
        List<TreeNode> list1 = new ArrayList<>();
        isNode(root, q, list1);
        int i = list.size() - 1;
        int j = list1.size() - 1;
        while(i >= 0 && j >= 0){
            if(list.get(i) == list1.get(j)){
                i--;
                j--;
            } else {
                break;
            }
        }
        return list.get(i + 1);
    }