题解 | #二叉搜索树的最近公共祖先#

using System;
using System.Collections.Generic;

/*
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode (int x)
    {
        val = x;
    }
}
*/

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        List<int> pList = new List<int>();
        List<int> qList = new List<int>();
        TreeNode t1 = root;
        while (t1.val != p) {
            pList.Add(t1.val);
            if (p < t1.val)
                t1 = t1.left;
            else
                t1 = t1.right;
        }
        pList.Add(t1.val);
        TreeNode t2 = root;
        while (t2.val != q) {
            qList.Add(t2.val);
            if (q < t2.val)
                t2 = t2.left;
            else
                t2 = t2.right;
        }
        qList.Add(t2.val);
        if (pList.Count > qList.Count) {
            for (int i = pList.Count - 1; i >= 0; --i) {
                for (int j = qList.Count - 1; j >= 0; --j) {
                    if (pList[i] == qList[j])
                        return pList[i];
                }
            }
        } else {
            for (int i = qList.Count - 1; i >= 0; --i) {
                for (int j = pList.Count - 1; j >= 0; --j) {
                    if (qList[i] == pList[j])
                        return pList[i];
                }
            }
        }

        return 0;
    }
}