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

思路

看到各位大佬的思路基本都是找到一个节点后再找父节点再找另外一个节点,思路听起来比较复杂,我在这里分享一个比较简单的思路:
首先对树进行两次遍历(可以优化成一次)找到这两个节点,同时记录根节点到这两个节点的路径, 然后对两个节点的路径进行遍历比较, 从
根节点开始比较, 最后一次两个路径上节点相同就是这两个节点的父节点.

java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if(root == null) return 0;
        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();
        findTrace(root, o1, stack1);      //获得根节点到o1的路径
        findTrace(root, o2, stack2);      //获得根节点到o2的路径
        int result = 0;
        int temp = 0;
        while(stack1.size()!=0 && stack2.size()!=0 &&  (temp = stack1.pollFirst()) == stack2.pollFirst()){result = temp;} //比较两个路径, 
                                                                                                          //出现不一致说明不是父节点了
        return result;
    }

    public static boolean findTrace(TreeNode node, int val, Deque<Integer> stack){
        if(node == null) return false;

        if(node.val != val){
            stack.offerLast(node.val);
            if(findTrace(node.left, val, stack)) return true;
            if(findTrace(node.right, val, stack)) return true;
            stack.pollLast();
            return false;
        } else {
            stack.offerLast(node.val);
            return true;
        }

    }
}