一. 题目描述
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
二. 题目分析
可使用递归解法,而只要是能用递归,也就是说能用栈来还原递归过程,因此方法不止一种。
使用栈来实现二叉树的遍历:首先在stack中压入当前的root,由于是前序遍历,故树是按照先根,然后左子树和后右子树进行访问,故pop取出一个结点,将它的value加入访问序列。之后压入它的右子树和左子树。直到stack为空。
三. 示例代码
递归解法:
#include
#include
using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL){} }; class Solution { public: void preorder(TreeNode *root, vector
&k) { if (root != NULL) { k.push_back(root->val); preorder(root->left, k); preorder(root->right, k); } } vector
preorderTraversal(TreeNode *root) { vector
temp; preorder(root, temp); return temp; } };
非递归解法(stack实现):
#include
#include
#include
using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL){} }; class Solution { public: vector
preorderTraversal(TreeNode *root) { vector
temp; temp.clear(); stack
k; if (root == NULL) return temp; k.push(root); while (!k.empty()) { TreeNode *node = k.top(); k.pop(); temp.push_back(node->val); if (node->right != NULL) k.push(node->right); if (node->left != NULL) k.push(node->left); } return temp; } };