No_236.cs

namespace LeetCode
{
    public class No_236
    {
        public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {
            Stack<TreeNode> next = new Stack<TreeNode>();
            next.Push(root);
            Stack<TreeNode> lowers = new Stack<TreeNode>();
            List<TreeNode> visited = new List<TreeNode>();
            bool h1 = false;

            while (next.Count != 0)
            {
                TreeNode cur = next.Peek();


                if (lowers.Count != 0 && lowers.Peek() == cur)
                {
                    lowers.Pop();
                    next.Pop();
                }
                else if (visited.Remove(cur))
                    next.Pop();
                else
                {
                    if (!h1)
                        lowers.Push(cur);
                    else
                        visited.Add(cur);

                    if (cur == p || cur == q)
                    {
                        if (h1) return lowers.Pop();
                        h1 = true;
                    }
                    if (cur.left == null && cur.right == null)
                    {
                        next.Pop();
                        if (lowers.Count != 0 && lowers.Peek() == cur)
                            lowers.Pop();

                    }
                    else
                    {

                        if (cur.right != null)
                            next.Push(cur.right);

                        if (cur.left != null)
                            next.Push(cur.left);
                    }
                }
            }
            return lowers.Pop();
        }
    }
}