题解 | #在二叉树中找到两个节点的最近公共祖先#
在二叉树中找到两个节点的最近公共祖先
https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116
方法：
先求路径，再找公共节点
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;
}
}
