首页 > 代码库 > Binary Tree Preorder Traversal

Binary Tree Preorder Traversal

Problem:

Given a binary tree, return the preorder traversal of its nodes‘ value.

For example:

Given binary tree {1, #, 2, 3},

return [1,2,3]

Note: Recursive solution is trivial, could you do it iteratively?

分析:

先序遍历的访问顺序是“中左右”,先遍历根节点,随后是左子树、右子树。每个节点第一次被访问时,直接加入遍历的序列中,此时左子树没有遍历,右子树也没有遍历,根据顺序需要先遍历左子树,左子树整个完成后遍历右子树,所以要将没有访问过右子树的根节点依次压入堆栈,在访问右子树分支的时候再弹出堆栈。

完整的逻辑是先从根节点开始走左子树,一直朝着左走到叶子节点,并将访问过的节点加入遍历过的序列中。而后,循环着查看堆栈顶部的元素,如果有右子树,则完整的遍历右子树,并在遍历前弹出栈顶元素;如果没有右子树,则直接弹出栈顶的元素。

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