[LeetCode 题解]: Binary Tree Preorder Traversal

前言

 

【LeetCode 题解】系列传送门:  http://www.cnblogs.com/double-win/category/573499.html

 

1.题目描述

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?

2. 题意

 

先序遍历二叉树,递归的思路是普通的,能否用迭代呢?

 

3. 思路

非递归思路:<借助stack>

    vector<int> preorderTraversal(TreeNode *root) {
stack<TreeNode* > st;
vector<int> vi;
vi.clear();
if(!root) return vi; st.push(root);
while(!st.empty()){
TreeNode *tmp = st.top();
vi.push_back(tmp->val);
st.pop();
if(tmp->right) st.push(tmp->right);
if(tmp->left) st.push(tmp->left);
}
return vi;
}

递归思路:

class Solution {
private:
vector<int> vi;
public:
vector<int> preorderTraversal(TreeNode *root) {
vi.clear();
if(!root) return vi;
preorder(root);return vi;
}
void preorder(TreeNode* root){
if(!root) return;
vi.push_back(root->val);
preorder(root->left);
preorder(root->right);
}
};

4.相关题目

(1)二叉树的中序遍历:

(2)二叉树的后序遍历:

(3) 二叉树系列文章:

[LeetCode 题解]: Binary Tree Preorder Traversal

作者:Double_Win

出处: http://www.cnblogs.com/double-win/p/3896010.html 

声明: 由于本人水平有限,文章在表述和代码方面如有不妥之处,欢迎批评指正~

上一篇:线段树区间求最大值(点更新)---I Hate It


下一篇:Mysql 创建用户并对其赋予操作权限