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

思路：两个节点之间的最短路径一定会经过两个节点的最小公共祖先，所以我们可以用LCA（最低公共祖先）的解法。不同于LCA的是，我们返回不只是标记，而要返回从目标结点递归回当前节点的路径。当遇到最小公共祖先的时候便合并路径。需要注意的是，我们要单独处理目标节点自身是最小公共祖先的情况。

Java代码实现如下：

public LinkedList
   
     helper(TreeNode n, TreeNode p, TreeNode q){    if(n == null){        return null;    }        LinkedList
    
      left = helper(n.left, p, q);    LinkedList
     
       right = helper(n.right, p, q);        // 当左右都为空时    if(left == null && right == null){        // 如果当前节点是目标节点，开启一条新路径        if(n == p || n == q){            LinkedList l = new LinkedList
      
       ();            l.add(n);            return l;        } else {        // 否则标记为空            return null;        }    // 如果左右节点都不为空，说明是最小公共祖先节点，合并两条路径    } else if(left != null && right != null){        finalPath.addAll(left);        finalPath.add(n);        Collections.reverse(right);        finalPath.addAll(right);        return left;    // 如果当前节点是目标结点，且某一个子树不为空时，说明最小公共祖先是节点自身    } else if (left != null){        left.add(n);        if(n == p || n == q){            finalPath.addAll(left);        }        return left;    } else {        right.add(n);        if(n == p || n == q){            finalPath.addAll(right);        }        return right;    }}
      
     
    
   

转载地址：https://blog.csdn.net/yyychocolate/article/details/108272341 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！