题解 | #在二叉树中找到两个节点的最近公共祖先#

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    //是否找到的标志
    public boolean flag=false;
    
    //求路径
    public void path(TreeNode root,Stack<TreeNode>stack,int obj){
        if(root==null||flag)
            return;
        stack.push(root);
        if(root.val==obj){
            flag=true;
            return;
        }
        //左右子树找路径
        path(root.left,stack,obj);
        path(root.right,stack,obj);
        if(flag)
            return;
        //该节点上没路径，出栈
        stack.pop();
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        
        //深度优先遍历
        Stack<TreeNode>stack1=new Stack<>();
        Stack<TreeNode>stack2=new Stack<>();
        path(root,stack1,o1);
        //重置标识
        flag=false;
        path(root,stack2,o2);
        while(stack1.size()>stack2.size())
            stack1.pop();
        while(stack2.size()>stack1.size())
            stack2.pop();
        while(stack1.peek()!=stack2.peek()){
            stack1.pop();
            stack2.pop();
        }
        return stack1.pop().val;

    }
}