Binary Tree Preorder Traversal

最后更新于:2022-04-01 22:56:28

**一. 题目描述** 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; } }; ~~~
';