题解 | #在二叉树中找到两个节点的最近公共祖先#

如何在二叉树中找到根节点到目标节点的路径

二叉树不像二叉搜索树一样有序，因此需要递归寻找左子树和右子树，看看有没有目标节点，因此需要一个变量记录是否找到目标节点，在每一层将当前节点加入路径，如果当前节点是目标节点，则直接返回，路径数组是作为参数传入，在每一层改变的，如果当前节点不是目标节点，则到左右子树中找目标节点，找到后就会直接返回，没有找到则会将路径的最后一个节点，也就是每层刚加入的节点去除，因此递归返回时，当前层路径数组中就只有刚加入的节点了。

参考

参考题解

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public boolean isFound = false;  // 判断是否有没有找到的标志
    private void getPath(TreeNode root, int target, ArrayList<Integer> path) {
        // 需要用递归回溯法查找路径
        if (root == null || isFound == true) {  // 如果找到了就不用往后找了
            return;
        }

        path.add(root.val);  // 当前节点加入路径
        if (root.val == target) {  // 如果找到则直接返回，此时path已经包含根节点到目标节点的路径了
            isFound = true;
            return;
        }

        // 如果没找到则到左右子树中查找目标节点
        getPath(root.left, target, path);
        getPath(root.right, target, path);

        if (isFound) {  // 左右子树找完后找到了目标节点，则直接返回
            return;
        }
        path.remove(path.size()-1);  // 如果没找到，去除当前增加的节点，因为每层没找到都会去除刚加入的节点，所以递归出来的时候，path中的最后一个元素就是刚加入的元素了。
        return;

    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
	    // 用LinkedList最后一个用例会超时
        ArrayList<Integer> pathP = new ArrayList<>();
        ArrayList<Integer> pathQ = new ArrayList<>();
        getPath(root, o1, pathP);
        isFound = false;  // 重置找到标志，寻找第二个目标值的路径
        getPath(root, o2, pathQ);
        int res = 0;
        for (int i = 0; i < pathP.size() && i < pathQ.size(); ++i) {
            int x = pathP.get(i);
            int y = pathQ.get(i);
            // 最后一个相同的点就是最近公共祖先
            if (x == y) {
                res = pathP.get(i);
            }
            else {
                break;
            }
        }
        return res;
    }
}