版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
题目
- Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree{1,#,2,3},
return[1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
题目大意
给定一棵二叉树，实现二叉树的前序遍历。
递归思想
思路
二叉树前序遍历的递归思想实现。顺序为：根 → 左 → 右。
代码
/*
* 二叉树前序遍历
*/
vector<int> preorderTraversal(TreeNode *root)
{
vector<int> v;
help_fun(v, root);
return v;
}
/*
* 前序遍历顺序为：根 → 左 → 右
*/
void help_fun(vector<int> &v, TreeNode *root)
{
if(root == NULL)return;
v.push_back(root->val); // 保存根节点的值
help_fun(v, root->left); // 递归遍历左子树
help_fun(v, root->right); // 递归遍历右子树
}
非递归思想
思路
非递归方法入栈的时候先压右子树，因为用的是栈，栈是后进先出，在循环中，先保存当前根结点，然后分别将当前结点的右、左结点入栈，出栈时先出左结点，这样就能继续遍历左结点的孩子结点。就实现了二叉树的前序遍历，即：根 → 左 → 右。
get(root -> val);// 根
inorder(root -> left);// 左子树
inorder(root -> right);// 右子树
代码
/*
* 模拟 根 → 左 → 右 遍历
*/
vector<int> preorderTraversal(TreeNode *root)
{
vector<int > v;
stack<TreeNode* > s;
if(root == NULL)return v;
s.push(root);
while(!s.empty())
{
TreeNode *cur;
cur = s.top();
s.pop();
v.push_back(cur->val); // 保存根节点
if(cur->right != NULL)
s.push(cur->right); // 压入右结点
if(cur->left != NULL)
s.push(cur->left); // 压入左结点
}
return v;
}
以上。
版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
