题解 | #二叉搜索树与双向链表#

/*
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode (int x)
    {
        val = x;
    }
}*/
using System.Collections.Generic;
class Solution
{
    public TreeNode Convert(TreeNode pRootOfTree)
    {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(pRootOfTree == null) return pRootOfTree;
        stack.Push(pRootOfTree);
        TreeNode cur;
        TreeNode pre = null;
        TreeNode head = pRootOfTree;
        bool isFirst = true;
        while(stack.Count != 0){
            cur = stack.Pop();
            if(cur != null){
                if(cur.right != null) stack.Push(cur.right);
                stack.Push(cur);
                stack.Push(null);
                if(cur.left != null) stack.Push(cur.left);
            }
            else{
                if(isFirst){
                    cur = stack.Pop();
                    head = cur;
                    pre = cur;
                    isFirst = false;
                }
                else{
                    cur = stack.Pop();
                    pre.right = cur;
                    cur.left = pre;
                    pre = cur;
                }
            }
        }
        return head;
    }
}