Tags

, ,

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1: recursion solution is easy. here is the code from Wiki

preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left) 
  preorder(node.right)

Solution 2: if we do it iteratively, the key part is that using stack to store all the tree nodes. stack is first in, last out. so when we scan the root, we push right child into the stack, to let it last out after all visits in left node.

        public List<int> preorderTraversal(TreeNode root)
        {
            var values = new List<int>();
            var mystack = new Stack<TreeNode>();
            if (root != null)
            {
                mystack.Push(root);
            }

            while (mystack.Count > 0)
            {
                var top = mystack.Pop();
                values.Add(top.val);

                if (top.right != null)
                {
                    mystack.Push(top.right);
                }
                if (top.left != null)
                {
                    mystack.Push(top.left);
                }
            }

            return values;
        }

Solution 3: can we reduce the space complexity more? yes if we can change the struct of the tree node. that is Morris Traversal Algorithm.

    public IList PreorderTraversal(TreeNode root) {
            var res = new List();

            while (root != null)
            {
                if (root.left != null)
                {
                    var pre = root.left;
                    while (pre.right != null && pre.right != root)
                    {
                        pre = pre.right;
                    }

                    if (pre.right == null)
                    {
                        pre.right = root;
                        res.Add(root.val);
                        root = root.left;
                    }
                    else
                    {
                        pre.right = null;
                        root = root.right;
                    }
                }
                else
                {
                    res.Add(root.val);
                    root = root.right;
                }
            }

            return res;     
    }