首页 > 代码库 > [LeetCode] Binary Tree Preorder/Inorder/Postorder Traversal

[LeetCode] Binary Tree Preorder/Inorder/Postorder Traversal

2024-07-07 19:09:41   215人阅读

前中后遍历 递归版

 1  /*  Recursive solution */
 2 class Solution {
 3 public:
 4     vector<int> preorderTraversal(TreeNode *root) {
 5         
 6         vector<int> result;
 7         preorderTraversal(root, result);
 8         
 9         return result;
10     }
11     
12     void preorderTraversal(TreeNode *root, vector<int>& result)
13     {
14         if(root == NULL) return;
15         result.push_back(root->val);
16         
17         preorderTraversal(root->left, result);
18         preorderTraversal(root->right, result);
19     }
20     
21 };

 

 1  /*  Recursive solution */
 2 class Solution {
 3 public:
 4     vector<int> inorderTraversal(TreeNode *root) {
 5         
 6         vector<int> result;
 7         inorderTraversal(root, result);
 8         
 9         return result;
10     }
11     
12     void inorderTraversal(TreeNode *root, vector<int>& result)
13     {
14         if(root == NULL) return;
15         
16         inorderTraversal(root->left, result);
17         result.push_back(root->val);
18         inorderTraversal(root->right, result);
19     }
20     
21 };

 

 1  /*  Recursive solution */
 2 class Solution {
 3 public:
 4     vector<int> postorderTraversal(TreeNode *root) {
 5         
 6         vector<int> result;
 7         postorderTraversal(root, result);
 8         
 9         return result;
10     }
11     
12     void postorderTraversal(TreeNode *root, vector<int>& result)
13     {
14         if(root == NULL) return;
15         
16         postorderTraversal(root->left, result);
17         result.push_back(root->val);
18         postorderTraversal(root->right, result);
19     }
20     
21 };

下面是迭代版本

1 preorder： 节点入栈一次， 入栈之前访问。

2 inorder：节点入栈一次，出栈之后访问。

3 postorder：节点入栈2次，第二次出战后访问。

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

 

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

 

后续， 用bStack标记是否是第一次访问，如果是第一次访问，再次入栈，否则直接访问，记得将P = NULL；

 1 class Solution {
 2 public:
 3     vector<int> postorderTraversal(TreeNode *root) {
 4         
 5         vector<int> result;
 6         stack<TreeNode*> stack;
 7         std::stack<bool> bStack;
 8         
 9         TreeNode *p = root;
10         bool isFirst;
11         
12         while( NULL != p || !stack.empty())
13         {
14             while(NULL != p)
15             {
16                 stack.push(p);
17                 bStack.push(false);
18                 p = p->left;
19             }
20             
21             if(!stack.empty())
22             {
23                 p= stack.top();
24                 stack.pop();
25                 
26                 isFirst = bStack.top();
27                 bStack.pop();
28                 
29                 if(isFirst == 0)
30                 {
31                     stack.push(p);
32                     bStack.push(true);
33                     p=p->right;
34                 }
35                 else
36                 {
37                     result.push_back(p->val);
38                     p = NULL;
39                 }
40                 
41             }
42         }
43         
44         return result;
45     }
46     
47 };

 

 

 

 


联系
我们