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;}