144. Binary Tree Preorder Traversal

发表于 | 分类于

每日一题 2019 - 05 - 10

题目：

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

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

解法：

这个题让求出二叉树的先序遍历（不使用递归），由于前面已经写过二叉树的层次遍历，所以在写这个先序遍历非递归时候，不是很吃力；

整体来说，解法就是使用数据结构栈，每一次先存放当前节点的右子树再存放左子树，因为访问的时候是率先访问左子树的，而栈又是先进后出，所以要先放右再放左，每次弹出栈中最上层元素，直到栈为空，即为完成遍历；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> q ;
        vector<int> temp ;
        if(root == NULL)
        {
            return temp ;
        }
        q.push(root);
        while(!q.empty())
        {
            TreeNode* now = q.top();
            q.pop();
            temp.push_back(now->val);
            if(now->right)
            {
                q.push(now->right);
            }
            if(now->left)
            {
                q.push(now->left);
            }
        }
        return temp ;
    }
};
0%
undefined