LeetCode 中序遍历二叉树

中序遍历是指将二叉树转换成 [左边节点],[中间节点],[右边节点] 格式的一维数组，以下为实现

        #region 使用后进先出集合实现【不使用额外对象封装实现】
        
        public IList<int> InorderTraversal(TreeNode root)
        {
            var rets = new List<int>();

            var stack = new Stack<TreeNode>();
            if (root != null)
                stack.Push(root);
            while (stack.Count > 0)
            {
                var node = stack.Peek();
                if (node.left != null)
                {
                    stack.Push(node.left);
                    node.left = null;
                }
                else
                {
                    rets.Add(node.val);
                    stack.Pop();
                    if (node.right != null)
                    {
                        stack.Push(node.right);
                    }
                }
            }
            return rets;
        }

        #endregion

        #region 使用后进先出集合实现【不更改输入元素实现】

        public class Node
        {
            public Node(TreeNode treeNode)
            {
                TreeNode = treeNode;
                Left = true;
            }
            public TreeNode TreeNode { get; set; }
            public bool Left { get; set; }
        }
        public IList<int> InorderTraversal(TreeNode root)
        {
            var rets = new List<int>();

            var stack = new Stack<Node>();
            if (root != null)
                stack.Push(new Node(root));
            while (stack.Count > 0)
            {
                var node = stack.Peek();
                if (node.Left)
                {
                    node.Left = false;
                    if (node.TreeNode.left != null)
                    {
                        stack.Push(new Node(node.TreeNode.left)); //将最左边节点存入队列
                    }
                }
                else
                {
                    rets.Add(node.TreeNode.val);
                    stack.Pop(); //移除当前项
                    if (node.TreeNode.right != null)
                    {
                        stack.Push(new Node(node.TreeNode.right)); //将最右边节点存入队列
                    }
                }
            }

            return rets;
        }

        #endregion

        #region 递归解法
        public IList<int> InorderTraversal(TreeNode root)
        {
            var rets = new List<int>();
            if (root != null)
                InorderTraversal(root, rets);
            return rets;
        }

        private static void InorderTraversal(TreeNode root, List<int> rets)
        {
            if (root.left != null)
                InorderTraversal(root.left, rets);
            rets.Add(root.val);
            if (root.right != null)
                InorderTraversal(root.right, rets);
        }
        #endregion