返回信息流此题是求一棵二叉树的两个节点的最近公共祖先，我是考虑先用DFS来得到这两个指定节点的路径，保存在List中，然后对这两个list，进行逐一比较，如果得到最先公共祖先。代码如下：
Class TreeNode
{
TreeNode left;
TreeNode right;
int val;
TreeNode(int x)
{
val = x;
}
}
public class Solution
{
public static TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q)
{
Stack<TreeNode> path = new Stack<TreeNode>();
List<List<TreeNode>> result = new ArrayList<List<TreeNode>>();
path(root,p,path,result);
path.removeAllElements();
path(root,q,path,result);
System.out.println(result.size());
List<TreeNode> l1 = result.get(0);
List<TreeNode> l2 = result.get(1);
System.out.println(l1.size() + " " + l2.size());
int length = l1.size() < l2.size() ? l1.size() : l2.size();
System.out.println(length);
TreeNode node = null;
while(length -- > 0)
{
if(l1.get(length).val == l2.get(length).val)
{
node = l1.get(length);
break;
}
//length--;
}
System.out.println(node.val);
return node;
}
@SuppressWarnings("unchecked")
public static boolean path(TreeNode root,TreeNode node,Stack<TreeNode> path,List<List<TreeNode>> result)
{
if(root == null)
return false;
path.push(root);
if(root.val == node.val)
{
result.add((Stack<TreeNode>)(path.clone()));
return true;
}
if(path(root.left,node,path,result))
return true;
if(path(root.right,node,path,result))
return true;
path.pop();
return false;
}
/*public static void main(String[] args)
{
TreeNode root = new TreeNode(5);
TreeNode l1 = new TreeNode(7);
TreeNode r1 = new TreeNode(8);
TreeNode l11 = new TreeNode(9);
TreeNode r11 = new TreeNode(10);
root.left = l1;
root.right = r1;
l1.left = l11;
l1.right = null;
r1.left = r11;
r1.right = null;
lowestCommonAncestor(root,l11,r1);
}*/ //测试用的
}
上面的代码基本的例子是可以过的吗，但是放在Leetcode上一跑，发现出现了栈溢出的情况，就是因为节点一多，递归的时候会将很多中间节点保存在栈中，就会出现这个问题，就问大神们如何改这个代码，最好别改我的思路。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #88539同步于 2015/12/10
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
LeetCode 236题 Lowest Common Ancestor of a Binary Tree
sun111
2015/12/10镜像同步6 回复
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
这么写呢
int dfs(tree *root,tree *target1,tree *target2,tree **result){
if(root == NULL)
return 0;
if(root == target1 || root == target2)
return 1;
int ret = dfs(root->left,target1,target2,result);
ret += dfs(root->right,target1,target2,result);
if(ret == 2){ //找到最近公共祖先
*result = root;
return 0;
}
return ret;
}
treenode *ret;
dfs(root,p1,p2,&ret); // ret 为答案
【 在 sun111 的大作中提到: 】
: 此题是求一棵二叉树的两个节点的最近公共祖先，我是考虑先用DFS来得到这两个指定节点的路径，保存在List中，然后对这两个list，进行逐一比较，如果得到最先公共祖先。代码如下：
: Class TreeNode
: {
: ...................
【 在 inaadversity 的大作中提到: 】
: 这么写呢
: [code=c]
: int dfs(tree *root,tree *target1,tree *target2,tree **result){
: ...................
看C++有点累，仁兄能讲下大致思路吗？
两个节点在公共祖先的两个分支上
后序遍历，如果遇到target之一，就返回1，遇到空返回0
如果在某个节点处，左右分支各返回1，那这个节点就是最近公共祖先，把公共祖先的位置记录下来，返回0。
static TreeNode result;
static int dfs(TreeNode root,TreeNode target1,TreeNode target2){
if(root == null)
return 0;
if(root == target1 || root == target2)
return 1;
int ret = dfs(root.left, target1, target2);
ret += dfs(root.right, target1, target2);
if(ret == 2){
result = root;
return 0;
}
return ret;
}
【 在 sun111 的大作中提到: 】
: 看C++有点累，仁兄能讲下大致思路吗？
【 在 inaadversity 的大作中提到: 】
: 两个节点在公共祖先的两个分支上
: 后序遍历，如果遇到target之一，就返回1，遇到空返回0
: 如果在某个节点处，左右分支各返回1，那这个节点就是最近公共祖先，把公共祖先的位置记录下来，返回0。
: ...................
恩，我再想下用java实现下
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
if(p==root||q==root){
return root;
}
TreeNode l = lowestCommonAncestor(root.left,p,q);
TreeNode r = lowestCommonAncestor(root.right,p,q);
if(l!=null&&r!=null){
return root;
}
return (l!=null)?l:r;
}
发现了另一个问题：
public static boolean path(TreeNode root,TreeNode node,Stack<TreeNode> path,List<List<TreeNode>> result)
{
if(root == null)
return false;
path.push(root);
if(root.val == node.val)
{
result.add((Stack<TreeNode>)(path.clone()));
return true;
}
if(path(root.left,node,path,result))
return true;
if(path(root.right,node,path,result))
return true;
path.pop();
return false;
}
}
判断两个节点是否相同，你用其val域判断，但是有可能测例中有val一样的节点。
如果是这样的话，那么就会有错误结果。
看了你的递归，你把List<List<TreeNode>> result我猜这个变量也作为参数传进去，往栈里面放很占空间（因为你List里面套了List），我试着只用了一层List。很容易就过了。
也许你应该用没过的测例试一下。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
LinkedList<TreeNode> stack1 = new LinkedList<TreeNode>();//The path for p;
LinkedList<TreeNode> stack2 = new LinkedList<TreeNode>();//The path for q;
search(root, p, stack1);
search(root, q, stack2);
TreeNode node1 = stack1.pollLast();
TreeNode node2 = stack2.pollLast();
TreeNode res = null;
while(node1 == node2){
res = node1;
node1 = stack1.pollLast();
node2 = stack2.pollLast();
}
return res;
}
private boolean search(TreeNode root, TreeNode node, LinkedList<TreeNode> stack){
if(root != null)
stack.push(root);
else
return false;
if(node == root){
return true;
}
if(search(root.left, node, stack))
return true;
if(search(root.right, node, stack))
return true;
stack.pop();
return false;
}
【 在 sun111 的大作中提到: 】
: 此题是求一棵二叉树的两个节点的最近公共祖先，我是考虑先用DFS来得到这两个指定节点的路径，保存在List中，然后对这两个list，进行逐一比较，如果得到最先公共祖先。代码如下：
: Class TreeNode
: {
: ...................