本文共 2240 字，大约阅读时间需要 7 分钟。

思路：这里来说，我的思路是用递归回溯把每个节点的路径都找出来。代码经过一点小小的手工测试，感觉是对的。但是，leetcode上给我1w个数的测试，然后栈就崩溃了。。在上面看到一个大神的解答，仅仅几行代码，足以看出他对递归的理解不是我能达到的。

import java.util.ArrayList;import javax.sound.midi.Soundbank;class TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int x) { val = x; left=right=null;}}public class Solution {
       public static void main(String args[])    {        TreeNode root=new TreeNode(1);        TreeNode temp=new TreeNode(2);        temp.right=new TreeNode(4);        temp.right.left=new TreeNode(5);        root.left=temp;        root.right=new TreeNode(3);        Solution so=new Solution();        TreeNode res=so.lowestCommonAncestor(root, temp.right, temp.right.left);        System.out.println(res.val);    }    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {        ArrayList
   
     pathsP=new ArrayList
    
     ();        ArrayList
     
       pathsQ=new ArrayList
      
       ();        findPath(root, p, pathsP);        findPath(root, q, pathsQ);        if(pathsP.size()==1||pathsQ.size()==1)        {            return root;        }        int min=pathsP.size()
       
         paths)    {        if(root==null)        {            return false;        }        paths.add(root);        if(root.val==target.val)        {            return true;        }        else        {            if(findPath(root.left, target, paths))            {                return true;            }else if(findPath(root.right, target, paths))            {                return true;            }            else            {                paths.remove(root);                return false;            }        }    }}
       
      
     
    
   

大神的解答

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        if(!root)            return NULL;        if(root == p || root == q)            return root;        // Check if left contains p or q        TreeNode* left = lowestCommonAncestor(root->left, p, q);        // Check if right contains p or q        TreeNode* right = lowestCommonAncestor(root->right, p, q);        // if left and right containsp or q the it'sthe LCA        if(left && right)            return root;        return left ? left : right;            }

转载地址：http://vbuvb.baihongyu.com/