Iterative solution with stack


  • 0

    From the view of compiler, a function call is implemented by a stack. So it is not too difficult to convert a recursive solution into an iterative one with the help of a stack.
    In my solution, to tell whether the left child is already visited, i set the left to null when the left child is pushed into the stack.

    public class Solution {
        public IList<int> InorderTraversal(TreeNode root) {
            var result = new List<int>();
            if (root == null) {
                return result;
            }
            
            var stack = new Stack<TreeNode>();
            stack.Push(root);
            
            while (stack.Count > 0) {
                var top = stack.Peek();
                if (top.left != null) {
                    stack.Push(top.left);
                    top.left = null;
                    continue;
                }
                
                stack.Pop();
                result.Add(top.val);
                if (top.right != null) {
                    stack.Push(top.right);
                }
            }
            
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.