题目描述

144. Binary Tree Preorder Traversal 94. Binary Tree Inorder Traversal 145. Binary Tree Postorder Traversal

前序排列 :根-左-右

中序排列: 左-根-右

后序排列:左-右-根

 

参考答案

 1 // PreOrder
 2 /**
 3  * Definition for a binary tree node.
 4  * struct TreeNode {
 5  *     int val;
 6  *     TreeNode *left;
 7  *     TreeNode *right;
 8  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 9  * };
10  */
11 class Solution {
12 private:
13         vector<int> res;
14 
15 public:
16     vector<int> preorderTraversal(TreeNode* root) {
17         foo(root);
18         return res;
19     }
20     void foo(TreeNode* root){
21         if(root == NULL)
22             return;
23         
24         res.push_back(root->val);
25         foo(root->left);
26         foo(root->right);
27     }
28 };
29 
30 // InOrder
31 class Solution {
32 public:
33     vector<int> inorderTraversal(TreeNode* root) {
34         if(root == NULL){
35             return vector<int>();
36         }
37         vector<int> result; // 创建结果
38         stack<TreeNode *> s;// 创建堆栈
39         TreeNode *p = root; // 临时让p为root
40         // 寻找p最左边的node
41         while(p!=NULL){
42             s.push(p); // 从root开始，将左边的node推入stack 
43             p = p->left;// 更新p为左node
44         }
45         // s 为全是左节点的stack
46         // 对 s进行循环操作
47         while(!s.empty()){
48             // 将最最左边的，推入stack
49             p = s.top();
50             result.push_back(p->val);
51             s.pop(); // 自己消失了
52             // 然后观察这个的右边node
53             if(p->right != NULL){
54                 p = p->right;
55                 while(p!=NULL){ //观察node的左边
56                     s.push(p);
57                     p = p->left;
58                 }
59             }     
60         }
61         return result;
62     }
63 };
64 
65 // PostOrder
66 
67 class Solution {
68 public:
69     vector<int> postorderTraversal(TreeNode* root) {
70         if(root == NULL){
71             return vector<int>();
72         }
73         vector<int> result;
74         stack<TreeNode *> s;
75         
76         s.push(root);
77         while(!s.empty()){
78             TreeNode *temp = s.top();
79             result.push_back(temp->val);
80             s.pop();
81             if(temp->left!=NULL){
82                 s.push(temp->left);
83             }
84             if(temp->right!= NULL){
85                 s.push(temp->right);
86             }
87         }
88         reverse(result.begin(), result.end());
89         return result;
90         
91     }
92 };