二叉树的遍历

* 先根序遍历（非递归版）

 1 void PreOrder(TreeNode* root)
 2 { 
 3         stack<TreeNode*> s;
 4         TreeNode *p=root,*last_visit=NULL;
 5         while(p||s.size()>0)
 6         {
 7             if(p)//走到最左 边走边访问 并进栈
 8             {
 9                 cout<<p->val<<endl;
10                 s.push(p);
11                 p=p->left;
12             }
13             else//左边没有节点了
14             {
15                 p=s.top();//弹出上一个节点
16                 s.pop();
17                 p=p->right;//转向右子树
18             }
19         }        
20 }

* 中根序遍历（非递归版）

void InOrder(TreeNode* root)
{       
        stack<TreeNode*> s;
        TreeNode *p=root,*last_visit=NULL;
        while(p||s.size()>0)
        {
            if(p)//走到最左
            {
                s.push(p);
                p=p->left;
            }
            else//左边没有节点了
            {
                p=s.top();//弹出上一个节点
                s.pop();
                cout<<p->val<<endl;//访问栈中弹出的节点
                p=p->right;//转向右子树
            }
        }     
}

* 后根序遍历（非递归版）

 1 void PostOrder(TreeNode* root)
 2 {
 3         stack<TreeNode*> s;
 4         TreeNode *p=root,*last_visit=NULL;//last_visit指针记录上次访问过的值，因为后根序 根节点最后访问 所以未访问根节点时 根节点还未退栈 所以需要判别右子树是否访问过
 5         while(p||s.size()>0)
 6         {
 7             if(p)//走到最左
 8             {
 9                 s.push(p);
10                 p=p->left;
11             }
12             else//左边没有节点了
13             {
14                 p=s.top();//弹出上一个节点
15                 if(p->right&&p->right!=last_visit)//若上一个节点存在右子树 且 未被访问过 则转向右子树
16                 {
17                     s.push(p->right);//右子树进栈
18                     p=p->right->left;//再转向右子树的左子树
19                 }
20                 else//p的左右子树都不存在才进行访问
21                 {
22                     last_visit=s.top();//记录下来本节点已经访问过了
23                     cout<<s.top()->val<<endl;
24                     s.pop();//将访问过的节点退栈
25                     p=NULL;//指针指向空 下次进来判断栈内下一个元素
26                 }
27             }
28         }       
29 }

* 二叉树的层次遍历（利用队列）

 1 void LevelOrder(TreeNode * root)
 2 {        
 3         queue<TreeNode*> que;//队列
 4         TreeNode* p;
 5         que.push(root);//先将根节点放入队列
 6         while(!que.empty())//队列不空
 7         {
 8             p=que.front();//取出队头结点
 9             cout<<p->val<<endl;//访问队头结点
10             que.pop();//将队头结点从队列中移除
11             if(p->left)//若p存在左子树
12                 que.push(p->left);
13             if(p->right)//若p存在右子树
14             que.push(p->right);
15         }
16 }

应用：

1、利用层次遍历获得二叉树的深度

 1 int GetBiTDepth(TreeNode* root)
 2 {　　　　if(!root) return 0;
 3         queue<TreeNode*> que;
 4         TreeNode* p=root,*last=root;//初始化第一层最后一个节点为root
 5         que.push(p);
 6         int count=0;//记录层数
 7         while(!que.empty())//队列不空
 8         {
 9             p=que.front();//取出队头结点
10             que.pop();//将队头结点从队列中移除
11             if(p->left)//若p存在左子树
12                 que.push(p->left);
13             if(p->right)//若p存在右子树
14                 que.push(p->right);
15             if(p==last)
16             {
17                 count++;//若遇到本层最后一个节点 层数+1
18                 last=que.back();//下一层最后一个节点为队列的尾部
19             }
20         }
21         return count;
22 }

2、递归求树的深度

 int GetBiTDepth(TreeNode* root)
    {
        if(root==NULL) return 0;
        else
        {
          int leftDepth=GetBiTDepth(root->left);
          int rightDepth=GetBiTDepth(root->right);
          return leftDepth>rightDepth?leftDepth+1:rightDepth+1;//树的深度为子树的最大高度加根节点
        }      
    }

3、leetcode 107题给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

 1 //法1 利用stl中的queue库    
 2 vector<vector<int>> levelOrderBottom(TreeNode* root) {
 3         vector<vector<int>> result;
 4         if(!root) return result;
 5         queue<TreeNode*> que;
 6         TreeNode* p=root,*last=root;//初始化第一层最后一个节点为root
 7         que.push(p);
 8         vector<int> level_result;
 9         while(!que.empty())//队列不空
10         {
11             p=que.front();//取出队头结点
12             level_result.push_back(p->val);
13             que.pop();//将队头结点从队列中移除
14             if(p->left)//若p存在左子树
15                 que.push(p->left);
16             if(p->right)//若p存在左子树
17                 que.push(p->right);
18             if(p==last)
19             {
20                 result.push_back(level_result);
21                 level_result.clear();
22                 last=que.back();//下一层最后一个节点为队列的尾部
23             }
24         }
25         reverse(result.begin(),result.end());
26         return result;
27     }

 1     //法2 利用数组模拟queue
 2     vector<vector<int>> levelOrderBottom(TreeNode* root) {
 3         vector<vector<int>> result;
 4         vector<int> level_result;
 5         if(!root) return result;
 6         TreeNode* queue[10000];
 7         TreeNode *p;
 8         int rear=-1,front=-1;
 9         int last=0;//代表每一层的最后一个
10         queue[++rear]=root;
11         while(front<rear)//队列不空
12         {
13             p=queue[++front];//将队头结点从队列中移除
14             level_result.push_back(p->val);
15             if(p->left)//若p存在左子树
16                 queue[++rear]=p->left;
17             if(p->right)//若p存在右子树
18                 queue[++rear]=p->right;
19             if(front==last)//当前节点是本层最后一个
20             {
21                 result.push_back(level_result);
22                 level_result.clear();
23                 last=rear;//下一层最后一个节点为队列的尾部
24             }
25         }
26         reverse(result.begin(),result.end());//逆置
27         return result;
28     }

4、leetcode 第105题根据一棵树的前序遍历与中序遍历构造二叉树

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10  //通过前序确定根节点 然后通过中序划分左子树具有的元素 右子树具有的元素 然后递归
11 class Solution {
12 public:
13     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
14        if(preorder.empty())return NULL;
15        return buildTreeHelper(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
16     }
17     TreeNode* buildTreeHelper(vector<int>& preorder, vector<int>& inorder,int ps,int pe,int is,int ie)
18     {
19         //ps pe分别为 preorder 的第一个元素的下标和最后一个元素的下标
20         //is ie分别为 inorder 的第一个元素的下标和最后一个元素的下标
21 
22         TreeNode* node=new TreeNode(preorder[ps]);
23         int cut;//中根序 根节点所在的地方 
24         for(cut=is;cut<ie&&inorder[cut]!=preorder[ps];cut++);//找到分割点
25         int l_len=cut-is;//左子树长度
26         int r_len=ie-cut;//右子树长度
27 
28         // cout<<cut<<" "<<l_len<<" "<<r_len<<" "<<endl;
29         // print_vector(preorder,ps+1,ps+l_len);//先根序序列 左子树的部分
30         // print_vector(inorder,is,is+l_len-1);//中根序序列 左子树的部分
31         // print_vector(preorder,pe-r_len+1,pe);//先根序序列 右子树的部分
32         // print_vector(inorder,ie-r_len+1,ie);//中根序序列 右子树的部分
33 
34         if(l_len) //若存在左子树 则对左子树进行递归
35             node->left=buildTreeHelper(preorder,inorder,ps+1,ps+l_len,is,is+l_len-1);
36         else 
37             node->left=NULL;
38         if(r_len) //若存在右子树 则对右子树进行递归
39             node->right=buildTreeHelper(preorder,inorder,pe-r_len+1,pe,ie-r_len+1,ie);
40         else 
41             node->right=NULL;
42         return node;
43     }
44     // void print_vector(vector<int>& v,int s,int e)
45     // {
46     //     int i=s;
47     //     for(;i<=e;i++)
48     //         cout<<v[i]<<" ";
49     //     cout<<endl;
50     // }
51 };

5、leetcode 第106题根据一棵树的中序遍历与后序遍历构造二叉树

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10  //类似 先序与中序建立二叉树
11  //后序遍历列表最后一个节点为根节点 
12  //在中序中 根节点前的是左子树(is,is+l_len-1) 根节点右边的是右子树(ie-r_len+1,ie)
13  //在后序中 (pe-1-r_len+1,pe-1)为右子树,(ps,ps+l_len-1)为左子树
14 class Solution {
15 public:
16 TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
17        if(postorder.empty())return NULL;
18        return buildTreeHelper(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
19     }
20     TreeNode* buildTreeHelper(vector<int>& inorder, vector<int>& postorder,int is,int ie,int ps,int pe)
21     {
22         //is ie分别为 inorder 的第一个元素的下标和最后一个元素的下标
23         //ps pe分别为 postorder 的第一个元素的下标和最后一个元素的下标
24       
25         TreeNode* node=new TreeNode(postorder[pe]);
26         int cut;//中根序 根节点所在的地方 
27         for(cut=is;cut<ie&&inorder[cut]!=postorder[pe];cut++);//找到分割点
28         int l_len=cut-is;//左子树长度
29         int r_len=ie-cut;//右子树长度
30 
31         // cout<<cut<<" "<<l_len<<" "<<r_len<<" "<<endl;
32         // print_vector(postorder,ps,ps+l_len-1);//后根序序列 左子树的部分
33         // print_vector(inorder,is,is+l_len-1);//中根序序列 左子树的部分
34         // print_vector(postorder,pe-r_len,pe-1);//后根序序列 右子树的部分
35         // print_vector(inorder,ie-r_len+1,ie);//中根序序列 右子树的部分
36 
37         if(l_len) //若存在左子树 则对左子树进行递归
38             node->left=buildTreeHelper(inorder,postorder,is,is+l_len-1,ps,ps+l_len-1);
39         else 
40             node->left=NULL;
41         if(r_len) //若存在右子树 则对右子树进行递归
42             node->right=buildTreeHelper(inorder,postorder,ie-r_len+1,ie,pe-r_len,pe-1);
43         else 
44             node->right=NULL;
45         return node;
46     }
47     // void print_vector(vector<int>& v,int s,int e)
48     // {
49     //     int i=s;
50     //     for(;i<=e;i++)
51     //         cout<<v[i]<<" ";
52     //     cout<<endl;
53     // }
54 };

6、leetcode 第958题二叉树完全性检验

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10  //层次遍历 若出现空节点 则此节点之后不能再出现非空节点 否则不是完全二叉树
11 class Solution {
12 public:
13     bool isCompleteTree(TreeNode* root) {
14         TreeNode* queue[200],*p;
15         int rear=-1,front=-1;
16         queue[++rear]=root;
17         while(front<rear)
18         {
19             p=queue[++front];
20             if(p)//若节点非空 入队
21             {
22                 queue[++rear]=p->left;
23                 queue[++rear]=p->right;
24             }
25             else//若节点为空 则判别队列中是否有非空节点 有则不是完全二叉树
26             {
27                 while(front<rear)
28                 {
29                     p=queue[++front];
30                     if(p) return false;
31                 }
32             }
33         }
34         return true;
35     }
36 };

7、递归统计二叉树的叶子节点数、双分支节点数、单分支节点数、所有节点数

 1 class Solution {
 2 public:
 3     //递归统计所有节点
 4     int countNodes(TreeNode* root) {
 5        if(root==NULL) return 0;//如果节点为空
 6        else if(root->left||root->right) return countNodes(root->left)+countNodes(root->right)+1;//如果存在左子树或右子树
 7        else return 1;//如果不存在左右子树
 8     }
 9      //递归统计所有双分支节点
10     int countNodes(TreeNode* root) {
11        if(root==NULL) return 0;//如果节点为空 
12        else if(root->left&&root->right) return countNodes(root->left)+countNodes(root->right)+1;//如果存在左子树右子树
13        else return countNodes(root->left)+countNodes(root->right);//如果不同时存在左右子树
14     }
15      //递归统计所有单分支节点
16     int countNodes(TreeNode* root) {
17        if(root==NULL) return 0;//如果节点为空 
18        else if((root->left&&!root->right)||(!root->left&&root->right)) 
19            return countNodes(root->left)+countNodes(root->right)+1;//如果左右子树不同时存在
20        else return countNodes(root->left)+countNodes(root->right);//如果不存在左右子树或同时存在左右子树
21     }
22      //递归统计所有叶子节点
23     int countNodes(TreeNode* root) {
24        if(root==NULL) return 0;//如果节点为空 
25        else if(!root->left&&!root->right) return 1;//如果节点没有孩子
26         else return countNodes(root->left)+countNodes(root->right);//如果节点有孩子
27     }
28 };

8、leetcode 第226题翻转二叉树

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* invertTree(TreeNode* root) {
13         if(!root) return NULL;
14         TreeNode* temp=root->left;
15         root->left=invertTree(root->right);//左孩子等于递归交换的右子树
16         root->right=invertTree(temp);//右孩子等于递归交换的左子树
17         return root;
18     }
19 };

二叉树的遍历

* 先根序遍历（非递归版）

* 中根序遍历（非递归版）

* 后根序遍历（非递归版）

* 二叉树的层次遍历（利用队列）

应用：

1、利用层次遍历 获得二叉树的深度

2、递归求树的深度

3、leetcode 107题 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

4、leetcode 第105题 根据一棵树的前序遍历与中序遍历构造二叉树

5、leetcode 第106题 根据一棵树的中序遍历与后序遍历构造二叉树

6、leetcode 第958题 二叉树完全性检验

7、递归统计二叉树的叶子节点数、双分支节点数、单分支节点数、所有节点数

8、leetcode 第226题 翻转二叉树

1、利用层次遍历获得二叉树的深度

3、leetcode 107题给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

4、leetcode 第105题根据一棵树的前序遍历与中序遍历构造二叉树

5、leetcode 第106题根据一棵树的中序遍历与后序遍历构造二叉树

6、leetcode 第958题二叉树完全性检验

8、leetcode 第226题翻转二叉树