/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    Stack<TreeNode> SP = new Stack<TreeNode>();
        Stack<TreeNode> SQ = new Stack<TreeNode>();

        bool findP = false;//是否找到p
        bool findQ = false;//是否找到q

        List<TreeNode> listP = new List<TreeNode>();
        List<TreeNode> listQ = new List<TreeNode>();

        private void DFS(TreeNode root, int p, int q)
        {
            if (root != null)
            {
                if (findP && findQ)
                {
                    return;
                }

                if (!findP)
                {
                    SP.Push(root);
                }
                if (!findQ)
                {
                    SQ.Push(root);
                }

                if (root.val == p)
                {
                    //p结点寻找结束
                    findP = true;
                    listP = SP.ToList();
                }
                if (root.val == q)
                {
                    //q结点寻找结束
                    findQ = true;
                    listQ = SQ.ToList();
                }

                if (root.left != null)
                {
                    DFS(root.left, p, q);
                }
                if (root.right != null)
                {
                    DFS(root.right, p, q);
                }

                if (!findP)
                {
                    SP.Pop();
                }
                if (!findQ)
                {
                    SQ.Pop();
                }
            }
        }

        public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {
            if (root == null || p == null || q == null)
            {
                return null;
            }
            //采用深度优先搜索，找到p和q
            DFS(root, p.val, q.val);

            for (int i = 0; i < listP.Count; i++)
            {
                for (int j = 0; j < listQ.Count; j++)
                {
                    var nodep = listP[i];
                    var nodeq = listQ[j];
                    if (nodep.val == nodeq.val)
                    {
                        return nodep;
                    }
                }
            }
            return null;
        }
}