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

此文仅用于记录

这题告诉我，二叉树能用节点本身解决的就不要引入什么第三方的数据结构了，比如什么数组的：
题解里一位大佬的代码：

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) {
        return CommonAncestor(root, o1, o2).val; 
    }
    public TreeNode CommonAncestor (TreeNode root, int o1, int o2) {
        if (root == null || root.val == o1 || root.val == o2) { // 超过叶子节点，或者root为p、q中的一个直接返回
            return root;
        } 
        TreeNode left = CommonAncestor(root.left,o1,o2); // 返回左侧的p\q节点
        TreeNode right = CommonAncestor(root.right,o1,o2); // 返回右侧的p\q节点
        if (left == null) {  // 都在右侧
            return right;
        }
        if (right == null) { // 都在左侧
            return left;
        }
        return root; // 在左右两侧
    }
}

我的不通过代码，原因是遍历了不需要的节点，导致出现错误的父节点：

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        //遍历了不需要的多余节点
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        backTrack(root,o1,list1);
        backTrack(root,o2,list2);
        int result = list1.get(0);
        for(int i = 0;i < list1.size() && i < list2.size();i++){
            if(list1.get(i) == list2.get(i)){
                result = list1.get(i);
            }
        }
        System.out.println(list1 + "=-----------------="+list2);
        return result;
    }
    void backTrack(TreeNode root,int o,ArrayList<Integer> list){
        if(root.val != o){
            list.add(root.val);
        }
        else{
            return;
        }
        if(root.left != null){
            backTrack(root.left,o,list);
        }
        if(root.right != null){
            backTrack(root.right,o,list);
        }
    }