【手撕代码2】-二叉树中序遍历（递归/非递归）

1.递归

2.非递归的核心在于使用栈的先进后出

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<stack>
 4 using namespace std;
 5 
 6 struct treenode
 7 {
 8     int val;
 9     treenode* left;
10     treenode* right;
11 };
12 
13 //递归
14 void inorder(treenode *root)
15 {
16     if (root!=NULL)return;
17     inorder(root->left);
18     cout << root->val<<" ";
19     inorder(root->right);
20 
21 }
22 //非递归
23 void inorder2(treenode* root)
24 {
25     stack<treenode*> a;
26     a.push(root);
27     treenode* t=root->left;
28     while (t != NULL||!a.empty()) {
29         while (t != NULL)
30         {
31             a.push(t);
32             t = t->left;
33         }
34         if(!a.empty())
35         {
36             t = a.top();
37             cout << t->val<<" ";
38             a.pop();
39             if (t->right != NULL)a.push(t->right);
40         }
41     }
42 
43 }
44 int main()
45 {
46     treenode* root;
47     inorder(root);
48     inorder2(root);
49     
50     return 0;
51 }

详见 https://blog.csdn.net/czy47/article/details/81254984