Java找二叉树的公共祖先

描述：

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

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

方法一：

思路：情况一p或者q其中一个是root,直接返回root；情况二，p或者q分别在root的左右子树上，递归找到root，情况三，p和q都在左子树或右子树上，这样有可能是递归后得到的情况一，或者是递归后的情况二

//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。前提：q!=p
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
//思路：情况一p或者q其中一个是root,直接返回root；情况二，p或者q分别在root的左右子树上，递归找到root，
//情况三，p和q都在左子树或右子树上，这样有可能是递归后得到的情况一，或者是递归后的情况二
//csdn:
public class Test4 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p==root || q==root)return root;//情况一和情况二
        if (root==null)return null;
        TreeNode rootleft=lowestCommonAncestor(root.left,p,q);
        TreeNode rootright=lowestCommonAncestor(root.right,p,q);
        //情况三
        if(rootleft!=null && rootright!=null)return root;//情况三下的情况二
        //p和q都在左子树或右子树上，
        else if(rootleft!=null && rootright==null)return rootleft;
        else if(rootleft==null && rootright!=null)return rootright;
        return null;//没有找到
    }

}

方法二?

思路：我们用两个栈分别存储root到p和q经过的节点路径，当递归到某个节点时，这个节点的左右子树都没有p或者q,说明该节点不是路径上的节点，出栈，两个栈存储完毕后保证两个栈的大小长度一样，一块出栈，当出栈元素相同时就是交点

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        Stack<TreeNode> stack_q=new Stack<>();
        Stack<TreeNode>stack_p=new Stack<>();
        getStack(root,stack_p,p);//寻找从根节点到p节点路径
        getStack(root,stack_q,q);//寻找从根节点到q节点路径
        int size_p=stack_p.size();
        int size_q=stack_q.size();
        //保证连个栈的长度一样
        if(size_p>size_q){
            for (int i = 0; i < size_p-size_q; i++) {
                stack_p.pop();
            }
        } else if (size_p<size_q) {
            for (int i = 0; i < size_q - size_p; i++) {
                stack_q.pop();
            }
        }
            //一块出一个元素，当元素相同时就是交点
            while (stack_p!=null){
                if(stack_p.peek()==stack_q.peek())return stack_p.pop();
                else {
                    stack_p.pop();
                    stack_q.pop();
                }
            }
        return root;
    }
    public boolean getStack (TreeNode root,Stack<TreeNode> stack,TreeNode key){
        if(root==null)return false;
        stack.push(root);
        if(root==key)return true;
       boolean figleft=getStack(root.left,stack,key);
       if(figleft)return true;//左边找到了节点
       boolean figright=getStack(root.right,stack,key);
       if (figright)return true;//右边找到了节点
       stack.pop();//该节点的左右子树都没有寻找的节点，从栈上，或者路径上移除
       return false;
    }