236.二叉搜索树的公共祖先

236.二叉树的公共祖先

思路

看到题想的是找到两个点的各自路径利用stack保存，根据路径长度大小将两个stack的值对齐到同一层，之后同时出栈节点，若相同则找到祖先节点。但是效率不高

看了大佬代码，递归思想很难理解。

根据大佬代码思想写了一个便于理解的版本，分为四种情况，递归求解。

代码

简单方法

    Stack<TreeNode> stack=new Stack<>();public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {int deep_p=findDeep(root,p,1);Stack<TreeNode> stack_p=new Stack<>();stack_p.addAll(stack);stack.clear();int deep_q=findDeep(root,q,1);Stack<TreeNode> stack_q=new Stack<>();stack_q=stack;//将p作为长端if (deep_p<deep_q){int temp;Stack<TreeNode> stack1=new Stack<>();temp=deep_q;stack1.addAll(stack_q);stack_q.clear();deep_q=deep_p;stack_q.addAll(stack_p);stack_p.clear();deep_p=temp;stack_p.addAll(stack1);}while (deep_p>deep_q){stack_p.pop();deep_p--;}TreeNode node_q=stack_q.pop(),node_p=stack_p.pop();while (node_q!=node_p){node_q=stack_q.pop();node_p=stack_p.pop();}return node_q;}public int findDeep(TreeNode root,TreeNode node,int deep){stack.push(root);if (root==null) return 0;if (root==node) return deep;int left=findDeep(root.left,node,deep+1);if (left==0) stack.pop();int right=findDeep(root.right,node,deep+1);if (right==0) stack.pop();return   Math.max(left,right);}

大佬代码（比较难懂，O（n））

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q) return root;TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left == null) return right;if(right == null) return left;return root;}
}

思想简化代码（O(4*n),多了4次find）

public class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root==null) return null;if (p==root || q==root) return root;//第一种情况，p,q其中一个为祖先节点if (find(root.left,p) && find(root.left,q)){ //第二种情况，p,q在当前节点左侧return lowestCommonAncestor(root.left,p,q);}if (find(root.right,p) && find(root.right,q)){//第三种情况，p,q在当前节点右侧return lowestCommonAncestor(root.right,p,q);}//第四种情况，p,q在两边return root;}public boolean find(TreeNode root,TreeNode p){if (root==null) return false;if (root==p) return true;return find(root.left,p) || find(root.right,p);}}