二叉树 - 理论基础 - 递归遍历 - 迭代遍历 -统一遍历

二叉树基础

基础概念

  • 满二叉树的节点数

2^k-1

  • 完全二叉树

底层不一定满，但是底层的节点是连续的。

  • 平衡二叉树

左右子树的最大层数差不超过1

  • 搜索方式
    • 深度优先搜索（包括前序，中序，后序）
    • 广度优先搜索（层序迭代法）
  • 前序遍历 -> 中左右
  • 中序 -> 左中右
  • 后序 ->左右中

定义代码实现

1
2
3
4
5
6
struct TreeNode{
	int val;
	Treenode * left;
	Treenode * right;
	TreeNode(int x): val(x),left(NULL),right(NULL){}
}

递归遍历

  • 递归三部曲
    • 确定递归函数的参数和返回值
    • 确定中止条件
    • 确定单层递归的逻辑

前序 -> 中左右

思路

递归参数 ->cur vec

退出边界条件： cur 为空

代码

前中后的分别代码

  • 前序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 //递归
class Solution {
public:
    void traversal(TreeNode* cur,vector<int>&vec){
        if(cur ==NULL) return ;
        vec.push_back(cur->val);
        traversal(cur->left,vec);
        traversal(cur->right,vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root,result);
        return result;
    }
};
  • 中序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 //递归
class Solution {
public:
    void traversal(TreeNode* cur,vector<int>&vec){
        if(cur ==NULL) return ;
        
        traversal(cur->left,vec);
        vec.push_back(cur->val);
        traversal(cur->right,vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root,result);
        return result;
    }
};
  • 后续
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 //递归
class Solution {
public:
    void traversal(TreeNode* cur,vector<int>&vec){
        if(cur ==NULL) return ;
        traversal(cur->left,vec);
        traversal(cur->right,vec);
        vec.push_back(cur->val);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root,result);
        return result;
    }
};

迭代遍历

迭代遍历一定是先进后出顺序，先进后出顺序，入栈的时候例如前序遍历递归的时候是中左右，那么进栈操作的顺序就得是中右左，模拟一遍入栈出栈过程就可以完整理解

前序遍历代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 //迭代
class Solution {
public:

    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> ST;
        vector<int> result;
        if(root==NULL){
            return result;
        }
        ST.push(root);
        while(!ST.empty()){
            TreeNode* node =ST.top();
            ST.pop();
            result.push_back(node->val);
            if(node->right)ST.push(node->right);  //如果右子树不为空则进栈
            if(node->left)ST.push(node->left);
        }
        return result;
    }
};

后序遍历代码

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 //迭代
class Solution {
public:

    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> ST;
        vector<int> result;
        if(root==NULL){
            return result;
        }
        ST.push(root);
        while(!ST.empty()){
            TreeNode* node =ST.top();
            ST.pop();
            result.push_back(node->val);
            if(node->right)ST.push(node->right);  //如果右子树不为空则进栈
            if(node->left)ST.push(node->left);
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

中序遍历代码

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 //迭代法
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> ST;
        vector<int> result;
        TreeNode * cur=root;
        while(cur!=NULL||!ST.empty()){
            if(cur!=NULL){
                ST.push(cur);
                cur=cur->left;      //左节点进栈
            }
            else{
                cur=ST.top();       //左中
                ST.pop();
                result.push_back(cur->val);     //拿值
                cur=cur->right;     //右
            }
        }
        return result;
    }
};
赏