• 43.8%

https://leetcode.com/problems/binary-tree-preorder-traversal/#/description

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

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

##### 方法二：

1. Create an empty stack, Push root node to the stack.
2. Do following while stack is not empty.

2.1. pop an item from the stack and print it.
2.2. push the right child of popped item to stack.
2.3. push the left child of popped item to stack.

Dec 10th, 2017

##### 方法四：

morris traversal

O(1)空间复杂度 O(n)时间复杂度

https://discuss.leetcode.com/topic/44387/preorder-inorder-postorder-iterative-solution-by-c

Preorder、inorder、postorder iterative solution by c++

preorder:

inorder:

postorder:

https://discuss.leetcode.com/topic/2917/accepted-code-explaination-with-algo

Accepted code. Explaination with Algo.

1. Create an empty stack, Push root node to the stack.
2. Do following while stack is not empty.

2.1. pop an item from the stack and print it.
2.2. push the right child of popped item to stack.
2.3. push the left child of popped item to stack.

https://discuss.leetcode.com/topic/12515/3-different-solutions

3 Different Solutions

Recursive method with List as returning value:

Recursive method with Helper method to have a List as paramater, so we can modify the parameter and don’t have to instantiate a new List at each recursive call:

Iterative method with Stack:

https://discuss.leetcode.com/topic/5748/easy-c-solution-using-stack

Easy C++ solution using Stack

https://discuss.leetcode.com/topic/21936/4-solutions-in-c

4 solutions in c++

https://discuss.leetcode.com/topic/7976/very-simple-iterative-python-solution

Very simple iterative Python solution

Classical usage of stack’s LIFO feature, very easy to grasp:

https://discuss.leetcode.com/topic/6493/accepted-iterative-solution-in-java-using-stack

Accepted iterative solution in Java using stack.

Note that in this solution only right children are stored to stack.