【leetcode刷题笔记】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?

解题：应该是很简单的一道题，纠结了好久T_T

基本思路很简单，用栈模拟就可以了。首先根节点压栈，每次弹出栈顶元素，并把它的值存入返回值向量中。如果它的右子树不为空，就把右子树根节点压栈，左子树不为空也把左子数根节点压栈，注意一定是右左这样的顺序。

主要纠结在两个地方：

1. 结构体指针的初始化：

struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));

　　注意要给指针分配空间，使用malloc需要包含头文件#include<cstdlib>

2.每次压栈以后栈顶元素就变了，所以要先把栈顶元素pop到一个变量中，再继续后续操作。

代码如下：

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10  #include <iostream>
11  #include <stack>
12  #include <vector>
13  #include <cstdlib>
14  using namespace std;
15  struct TreeNode {
16      int val;
17      TreeNode *left;
18      TreeNode *right;
19      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
20  };
21 class Solution {
22 public:
23     vector<int> preorderTraversal(TreeNode *root) {
24        stack<TreeNode*>s;
25        vector<int>ans;
26        if(root == NULL)
27             return ans;
28        s.push(root);
29        while(!s.empty()){
30             struct TreeNode* temp = s.top();
31             s.pop();
32             ans.push_back(temp->val);
33             if(temp->right != NULL)
34                 s.push(temp->right);
35             if(temp->left != NULL){
36                 s.push(temp->left);
37             }
38        }
39         return ans;
40     }
41 };
42 int main(){
43     Solution so;
44     struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
45     struct TreeNode* root_l_c = (struct TreeNode*)malloc(sizeof(struct TreeNode));
46 
47     root->val = 2;
48     root_l_c->val = 3;
49 
50     root_l_c->left = NULL;
51     root_l_c->right = NULL;
52 
53     root->right = NULL;
54     root->left = root_l_c;
55     //cout << root->left->val<<endl;
56     so.preorderTraversal(root);
57 }

Java版本递归解法：

 1 public class Solution {
 2     public List<Integer> preorderTraversal(TreeNode root) {
 3         List<Integer> answer = new ArrayList<>();
 4         return preorderTraversalHelper(answer, root);
 5     }
 6     public List<Integer> preorderTraversalHelper(List<Integer> answer,TreeNode root) {
 7         if(root == null)
 8             return answer;
 9         answer.add(root.val);
10         answer = preorderTraversalHelper(answer,root.left);
11         answer = preorderTraversalHelper(answer,root.right);
12         return answer;           
13     }
14 }

一个小笔记是在eclipse里面使用List或者ArrayList的时候要加上

import java.util.ArrayList;import java.util.List;