Leecode[94] 二叉树的中序遍历

题目

非递归方式实现二叉树中序遍历

代码

public class Solution {
    public IList<int> InorderTraversal(TreeNode root) {
            var res = new List<int>();
            if (root == null)
            {
                return res;
            }

            var stack = new Stack<TreeNode>();
            while (root != null || stack.Count != 0)
            {
                while (root != null)
                {
                    // 先将节点追加到栈中，再访问左节点
                    stack.Push(root);
                    root = root.left;
                }

                if (stack.Count != 0)
                {
                    var node = stack.Pop();
                    res.Add(node.val);
                    root = node.right;
                }
            }

            return res;
    }
}

错误点

• root != null || stack.Count != 0 条件。先深度遍历左子节点。当子节点不存在时，从栈中弹出节点，并获取右子节点。
• stack.Push(root) Push 时机。需要先将当前节点追加到栈中，然后再获取子节点