递归-leetcode236. Lowest Common Ancestor of a Binary Tree

一、问题描述
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

二、解决思路
思路一：给定两节点p、q，要找到其公共父节点，通过枚举一些示例可以发现，pq两节点之间的关系无非是父子关系和拥有共同父节点，若是父子关系，则父节点是所要求的节点，若拥有共同父节点，公共父节点是所要求的节点，因此可以采用递归来解决，递归结束条件为当前节点为null
思路二：思路一采用递归，可以采用非递归思路来解决，要采用非递归的话，可以保存pq两节点的所有父节点，最后求出所要求的节点

三、算法实现
思路一

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中一节点为root节点
        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);
    }