144. Binary Tree Preorder Traversal

  • 43.8%

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

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

1
2
3
4
5
6
7
8
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?


方法一:

递归 O(n)时间 O(n)空间

1
2
3
4
5
6
7
8
9
10
11
12
// recursive, but it's trivial...
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
preTraversal(root, v);
return v;
}
void preTraversal(TreeNode* root, vector<int>& v){
if(!root) return;
v.push_back(root->val);
preTraversal(root->left, v);
preTraversal(root->right, v);
}
方法二:

迭代方法,使用栈,遍历先根再左后右。存入栈,先右后左。很好理解。

  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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
stack<TreeNode*> nodeStack;
vector<int> result;
//base case
if(root==NULL)
return result;
nodeStack.push(root);
while(!nodeStack.empty())
{
TreeNode* node= nodeStack.top();
result.push_back(node->val);
nodeStack.pop();
if(node->right)
nodeStack.push(node->right);
if(node->left)
nodeStack.push(node->left);
}
return result;

}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> stack;
stack.push(root);
while(!stack.empty()){
TreeNode* node = stack.top();
stack.pop();
res.push_back(node->val);
if(node->right)
stack.push(node->right);
if(node->left)
stack.push(node->left);
}
return res;
}
};

方法三:

使用栈,按照递归的方法遍历

我的代码实现:

Dec 10th, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stack;
TreeNode* cur = root;
while(stack.size() || cur){
if(cur){
res.push_back(cur->val);
stack.push(cur);
cur = cur->left;
}else{
TreeNode* tmp = stack.top();
stack.pop();
cur = tmp->right;
}
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> stack;
while(root || stack.size()){
if(root){
stack.push(root);
res.push_back(root->val);
root = root->left;
}else{
TreeNode* node = stack.top();
stack.pop();
root = node->right;
}
}
return res;
}
};

我的代码实现二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stack;
TreeNode* cur = root;
while(cur || stack.size()){
if(cur){
stack.push(cur);
res.push_back(cur->val);
cur = cur->left;
}else{
cur = stack.top();
stack.pop();
cur = cur->right;
}
}
return res;
}
};
方法四:

morris traversal

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// morris traversal, O(1) space
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
if(!root) return v;
TreeNode* temp = root, *prev;
while(temp){
if(!temp->left){
v.push_back(temp->val);
temp = temp->right;
}else{
prev = temp->left;
while(prev->right&&(prev->right != temp))
prev = prev->right;
if(!prev->right){
v.push_back(temp->val);
prev->right = temp;
temp = temp->left;
}else{
prev->right = NULL;
temp = temp->right;
}
}
}
}

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode* cur = root;
while(cur){
if(cur->left){
TreeNode* pre = cur->left;
while(pre->right && pre->right!=cur)
pre = pre->right;
if(pre->right==cur){
pre->right = NULL;
cur = cur->right;
}else{
res.push_back(cur->val);
pre->right = cur;
cur = cur->left;
}
}else{
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
};

迭代方法总结,值得学习

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

Preorder、inorder、postorder iterative solution by c++

preorder:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
std::stack<TreeNode*> temp;
while (root || !temp.empty()) {
while (root) {
temp.push(root);
res.push_back(root->val);
root = root->left;
}
root = temp.top();
temp.pop();
root = root->right;
}
return res;
}

inorder:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
std::stack<TreeNode*> temp;
while (root || !temp.empty()) {
while (root) {
temp.push(root);
root = root->left;
}
root = temp.top();
temp.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}

postorder:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
std::stack<TreeNode*> temp;
while (root || !temp.empty()) {
while (root) {
temp.push(root);
res.insert(res.begin(),root->val);
root = root->right;
}
root = temp.top();
temp.pop();
root = root->left;
}
return res;
}

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
stack<TreeNode*> nodeStack;
vector<int> result;
//base case
if(root==NULL)
return result;
nodeStack.push(root);
while(!nodeStack.empty())
{
TreeNode* node= nodeStack.top();
result.push_back(node->val);
nodeStack.pop();
if(node->right)
nodeStack.push(node->right);
if(node->left)
nodeStack.push(node->left);
}
return result;

}
};

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

3 Different Solutions

Recursive method with List as returning value:

1
2
3
4
5
6
7
8
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> pre = new LinkedList<Integer>();
if(root==null) return pre;
pre.add(root.val);
pre.addAll(preorderTraversal(root.left));
pre.addAll(preorderTraversal(root.right));
return pre;
}

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:

1
2
3
4
5
6
7
8
9
10
11
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> pre = new LinkedList<Integer>();
preHelper(root,pre);
return pre;
}
public void preHelper(TreeNode root, List<Integer> pre) {
if(root==null) return;
pre.add(root.val);
preHelper(root.left,pre);
preHelper(root.right,pre);
}

Iterative method with Stack:

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> preorderIt(TreeNode root) {
List<Integer> pre = new LinkedList<Integer>();
if(root==null) return pre;
Stack<TreeNode> tovisit = new Stack<TreeNode>();
tovisit.push(root);
while(!tovisit.empty()) {
TreeNode visiting = tovisit.pop();
pre.add(visiting.val);
if(visiting.right!=null) tovisit.push(visiting.right);
if(visiting.left!=null) tovisit.push(visiting.left);
}
return pre;
}

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

Easy C++ solution using Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
if (root==NULL) {
return vector<int>();
}
vector<int> result;
stack<TreeNode *> treeStack;
treeStack.push(root);
while (!treeStack.empty()) {
TreeNode *temp = treeStack.top();
result.push_back(temp->val);
treeStack.pop();
if (temp->right!=NULL) {
treeStack.push(temp->right);
}
if (temp->left!=NULL) {
treeStack.push(temp->left);
}
}
return result;
}
};

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

4 solutions in c++

1
2
3
4
5
6
7
8
9
10
11
12
// recursive, but it's trivial...
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
preTraversal(root, v);
return v;
}
void preTraversal(TreeNode* root, vector<int>& v){
if(!root) return;
v.push_back(root->val);
preTraversal(root->left, v);
preTraversal(root->right, v);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// iterate, use stack to imitate recursive
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
if(!root) return v;
TreeNode* temp = root;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
temp = s.top();
s.pop();
v.push_back(temp->val);
if(temp->right) s.push(temp->right);
if(temp->left) s.push(temp->left);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
if(!root) return v;
TreeNode* temp = root;
stack<TreeNode*> s;
while(true){
while(temp){
v.push_back(temp->val);
if(temp->right) s.push(temp->right);
temp = temp->left;
}
if(s.empty()) break;
temp = s.top();
s.pop();
};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// morris traversal, O(1) space
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
if(!root) return v;
TreeNode* temp = root, *prev;
while(temp){
if(!temp->left){
v.push_back(temp->val);
temp = temp->right;
}else{
prev = temp->left;
while(prev->right&&(prev->right != temp))
prev = prev->right;
if(!prev->right){
v.push_back(temp->val);
prev->right = temp;
temp = temp->left;
}else{
prev->right = NULL;
temp = temp->right;
}
}
}
}

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:

1
2
3
4
5
6
7
8
9
10
def preorderTraversal(self, root):
ret = []
stack = [root]
while stack:
node = stack.pop()
if node:
ret.append(node.val)
stack.append(node.right)
stack.append(node.left)
return ret

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> preorderTraversal(TreeNode node) {
List<Integer> list = new LinkedList<Integer>();
Stack<TreeNode> rights = new Stack<TreeNode>();
while(node != null) {
list.add(node.val);
if (node.right != null) {
rights.push(node.right);
}
node = node.left;
if (node == null && !rights.isEmpty()) {
node = rights.pop();
}
}
return list;
}
谢谢你,可爱的朋友。