二叉树算法小结

---

二叉树的遍历

递归遍历

void pre(TreeNode *p){
        
        if(p!=NULL){
            vect.push_back(p->val);
            preorderTraversal(p->left);
            preorderTraversal(p->right);
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        pre(root);
        return vect;
        
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

其他呢`中序后续只改一下顺序即可

非递归遍历

思想:遇到左节点不空先入栈,并访问,空了就访问其右子树

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>result;
        TreeNode *p =root;
        TreeNode *s[Maxn];
        int top=-1;
        while(p || top!=-1){
            while(p){
                result.push_back(p->val);
                s[++top]=p;
                p=p->left;
            }
            p= s[top];
            top-=1;
            p=p->right;

        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

`中序遍历一样再pop之前访问即可

与之不同的是后序遍历`

    //思想:遇到左节点不空先入栈,并访问 直到左孩子为空,读栈顶元素:右孩子不同且违背访问过,将右孩子遍历.否则出栈访问.
    vector<int> preorderTraversal(TreeNode* root) {
         vector<int>result;
        TreeNode *p =root;
        TreeNode *s[Maxn];
        int top=-1;
        TreeNode *r ; //指向刚刚访问过的节点防止重复访问
        while(p || top!=-1){
            while(p){
                s[++top]=p;
                p=p->left;
            }
            p=s[top];
            if(p->right && p->right!=r)
                p=p->right;
            else{
                p= s[top--];
                result.push_back(p->val);
                r= p;
                p=NULL; //重置指针p 已经执行完访问该以这个节点为根的子树
            }

        }
        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

层序遍历

   vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>result;
        if(root==NULL){
            return result;
        }
         
         TreeNode *p =root;
         
         int  front=-1,rear=-1;
         TreeNode *que[Maxn];
         que[++rear]= p;
        vector<int> temp;
        temp.push_back(p->val);
        result.push_back(temp);
         while(front<rear){
             int l=front+1;
             int r= rear;
             vector<int> temp;//记录每一层的节点
             for(int i=l;i<=r;i++){
                 if(que[i]->left!=NULL){
                     que[++rear]=que[i]->left;
                    temp.push_back(que[i]->left->val);
                 }
                 if(que[i]->right!=NULL){
                     que[++rear]=que[i]->right;
                    temp.push_back(que[i]->right->val);
                 }

             }
             if(!temp.empty())
                result.push_back(temp);
             front=r;

         }
         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
34
35
36
37

二叉树的翻转

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
TreeNode* t;
class Solution {
public:
    void invert(TreeNode *root){
        if(root){
            invert(root->left);
            invert(root->right);
            t= root->left;
            root->left= root->right;
            root->right= t;
        }
    }
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL)return root;
        //采用分治思想
        invert(root);
        return root;


    }
};
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

判断二叉树是否对称

thought:思想：首先判断该节点是否左右对称 最外面 两两对比 里面两两对比 - 左空右不空 return 0

• 左不空右空 return 1
• 左右都空 return 1
• 左右都不空 且值相同 :继续执行
• 左右都不空 值不同return 0
  

    bool comp(TreeNode *left,TreeNode *right){
        if(left==NULL && right==NULL)return 1;
        else if(left==NULL && right!=NULL) return 0;
        else if(left!=NULL && right==NULL) return 0;
        else if(left->val!=right->val)return 0;
     //如果最后值都相同了 执行下面语句
        
        bool left_val= comp(left->left,right->right);
        bool right_val =comp(left->right,right->left   );
        //后序遍历 返回结果
        return left_val  && right_val;
        
    }
    bool isSymmetric(TreeNode* root) {
        if(root!=NULL){
            return comp(root->left,root->right);
        }
        else{
            return 1;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二叉树的最大深度

    void getlevel(TreeNode *p ,int hig){
        if(p){
            
            getlevel(p->left,hig+1);
            getlevel(p->right,hig+1);
            
        }else{
            level= max(hig,level);
        }
    }
    int maxDepth(TreeNode* root) {
        int h=0;
        getlevel(root,h);
        cout<<level<<endl;
        return level;
    } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

tip:后序遍历 直接递归求最大深度

    int maxDepth(TreeNode* root) {
        if(root){
            int l=maxDepth(root->left);
            int r=maxDepth(root->right);
            if(l>r){
                return l+1;
            }
            else{
                return r+1;
            }
        }else{
            return 0;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

tip或者利用层序遍历求level也可

二叉树的最小深度

    int minDepth(TreeNode* root) {
        if(root){
            int l= minDepth(root->left);
            int r= minDepth(root->right);
            if(root->left==NULL && root->right!=NULL) //左子树为空 右子树不为空
                return r+1;
            if(root->right==NULL && root->left!=NULL)
                return l+1;

  
        	return min(l,r)+1;
        }else{
            return 0;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

求二叉树的总结点数

    int calcNoe(TreeNode * p){
        if(p){
            int l= calcNoe(p->left);
            int r=calcNoe(p->right);
            return l+r+1;
        }else{
            return 0;
        }
    }
    int countNodes(TreeNode* root) {
        int nus= calcNoe(root);
        return nus;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

判断是否是平衡二叉树

tip:思路还是利用后序遍历来确定 从后序遍历来一步步的确定结果

    int getisdepth(TreeNode *p){
        if(p==NULL)return 0;
        
        int l= getisdepth(p->left);
        if(l==-1)return -1;
        int r=getisdepth(p->right);
        if(r==-1)return-1;
        int result;
        if(abs(l-r)>1) result=-1;
        else{
            result= max(l,r)+1;
        }
        return result;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

BFS模板

//模板题目


定义一个结构体描述节点的位置
还有一个判断合法的函数
最后利用bfs算法来遍历找到目的节点

#include
#include
using namespace std;
int m,n; //行列
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
const int Maxn=1e3+7;
int dis[Maxn][Maxn];//距离
char t [Maxn][Maxn];//图
typedef struct node{
    int row;
    int col;
    int step;//行走的步数
}node;
node arr[Maxn];
int sx,sy,fx,fy;
int legal(node a){
    if(a.col<0 | a.row>m| a.col>=n| a.row<0 &&dis[a.row][a.col]!=0)
        return 0;
    return 1;
}
int bfs(){
    int temp;
    queue<node> que;
    node now,next;
    now.row=sx;
    now.col=sy;
    que.push(now);
    dis[now.row][now.col]=0;
    while(!que.empty()){
        now= que.front();
        temp= t[now.row][now.col];
        que.pop();
        if(now.row==fx&&now.col==fy){
            //cout<<"very good you arrive it"<
            
            return dis[now.row][now.col] ;
        }
        for(int i=0;i<4;i++){
            next.row= now.row+dx[i];
            next.col= now.col+dy[i];
            next.step= now.step+1;
            if(t[next.row][next.col]==temp)continue;
            if(legal(next)){
                que.push(next);
                dis[next.row][next.col]=dis[now.row][now.col]+1;             
            }
        }
    }
    return -1;
}
int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++ )
        for(int j = 0;j < n;j ++ ){
            cin >> t[i][j];
            if(t[i][j] == 'A') sx = i,sy = j;
            if(t[i][j] == 'B') fx = i,fy = j;
        }

    // cout<<"start "<
    //  cout<<"end "<
     int n1= bfs();
     cout<<n1;
     //cout<<"the step is"<
     
//     for(int i = 0;i < n;i ++ ){
//         for(int j = 0;j < n;j ++ ){
//             cout<
//         }
//         cout<
// }

    return 0;
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83