个人技术分享

DAY18

二叉树的层序遍历

102二叉树的层序遍历

“队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。”

二叉树层序遍历模版：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     vector<vector<int>> levelOrder(TreeNode* root) {
15.         queue<TreeNode*> que;
16.         vector<vector<int>> result;
17.         if(root!=nullptr) que.push(root);
18.         while(!que.empty())
19.         {
20.             int size=que.size();
21.             vector<int> vec;
22.             for(int i=0;i<size;i++)
23.             {
24.                 TreeNode* node=que.front();
25.                 que.pop();
26.                 vec.push_back(node->val);
27.                 if(node->left) que.push(node->left);
28.                 if(node->right) que.push(node->right);
29.             }
30.             result.push_back(vec);
31.         } 
32.         return result;
33.     }
34. };

二叉树层序遍历递归模版：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     void order(TreeNode* node,vector<vector<int>> &result,int depth)
15.     {
16.         if(node==nullptr) return;
17.         if(result.size()==depth) result.push_back(vector<int>());
18.         result[depth].push_back(node->val);
19.         if(node->left) order(node->left,result,depth+1);
20.         if(node->right) order(node->right,result,depth+1);
21.     }
23.     vector<vector<int>> levelOrder(TreeNode* root) {
24.         vector<vector<int>> result;
25.         int depth=0;
26.         order(root,result,depth);
27.         return result;
28.     }
29. };

107二叉树的层序遍历II

递归法模版：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     void order(TreeNode* node,vector<vector<int>> &result,int depth)
15.     {
16.         if(node==nullptr) return;
17.         if(result.size()==depth) result.push_back(vector<int>());
18.         result[depth].push_back(node->val);
19.         if(node->left) order(node->left,result,depth+1);
20.         if(node->right) order(node->right,result,depth+1);
21.     }
22.     vector<vector<int>> levelOrderBottom(TreeNode* root) {
23.         vector<vector<int>> result;
24.         int depth=0;
25.         order(root,result,depth);
26.         reverse(result.begin(),result.end());
27.         return result;
28.     }
29. };

正常模版：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     vector<vector<int>> levelOrderBottom(TreeNode* root) {
15.         vector<vector<int>> result;
16.         queue<TreeNode*> que;
17.         if(root!=nullptr) que.push(root);
18.         while(!que.empty())
19.         {
20.             int size=que.size();
21.             vector<int> vec;
22.             for(int i=0;i<size;i++)
23.             {
24.                 TreeNode* node=que.front();
25.                 que.pop();
26.                 vec.push_back(node->val);
27.                 if(node->left) que.push(node->left);
28.                 if(node->right) que.push(node->right);
29.             }
30.             result.push_back(vec);
31.         }
32.         reverse(result.begin(),result.end());
33.         return result;
34.     }
35. };

199二叉树的右视图

现在变成一维vector的return result，该怎么写递归的模版呢？递归似乎更麻烦了。

先试试普通方法：

不行，思路错了：不能只遍历根节点和右孩子，因为会出现这种：

加了一句else if();新的问题又出现了：....

有想法了（“不如把思路逆转过来！”）：正常层序遍历，vector<vector<int>> result的每行，取最后一列，就是答案。怎么写语法呢？看答案吧：

代码随想录的思路要更直接：判断是否遍历到单层的最后面的元素，如果是，就放进result数组里，随后返回result就可以了。

那么如何知道“是否遍历到单层的最后面的元素”呢？我们有que.size()来记录这层树的节点个数！i 是节点的指针，那么i==size-1的话，就是答案；push_back.

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     vector<int> rightSideView(TreeNode* root) {
15.         queue<TreeNode*> que;
16.         vector<int> res;
17.         if(root!=nullptr) que.push(root);
18.         while(!que.empty())
19.         {
20.             int size=que.size();
21.             for(int i=0;i<size;i++)
22.             {
23.                 TreeNode* node=que.front();
24.                 que.pop();
25.                 if(i==size-1) res.push_back(node->val);
26.                 if(node->left) que.push(node->left);
27.                 if(node->right) que.push(node->right);
28.             }
29.         }
30.         return res;
31.     }
32. };

637二叉树的层平均值

语法怎么写

在层外和层里面操作就好啦：也就是：for里面和for外面。灵活一点！

数据上没有为难人，写好就通过了：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     vector<double> averageOfLevels(TreeNode* root) {
15.         queue<TreeNode*> que;
16.         vector<double> res;
17.         if(root!=nullptr) que.push(root);
18.         while(!que.empty())
19.         {
20.             int size=que.size();
21.             double sum=0;
22.             for(int i=0;i<size;i++)
23.             {
24.                 TreeNode* node=que.front();
25.                 que.pop();
26.                 sum+=node->val;
27.                 if(node->left) que.push(node->left);
28.                 if(node->right) que.push(node->right);
30.             }
31.             res.push_back(sum/size);
32.         }
33.         return res;
34.     }
35. };

牢记：有size来记录每层节点数量。

429 N叉树的层序遍历

Node的孩子不为空的时候，push_back就好，语法怎么写，尤其是这个children的迭代。。

哦：node->children[i]。因为它是一个vector，进一步，用for来迭代。记住for里面有个for，逻辑。

1. /*
2. // Definition for a Node.
3. class Node {
4. public:
5.     int val;
6.     vector<Node*> children;
8.     Node() {}
10.     Node(int _val) {
11.         val = _val;
12.     }
14.     Node(int _val, vector<Node*> _children) {
15.         val = _val;
16.         children = _children;
17.     }
18. };
19. */
21. class Solution {
22. public:
23.     vector<vector<int>> levelOrder(Node* root) {
24.     vector<vector<int>> res;
25.     queue<Node*> que;
26.     if(root!=nullptr) que.push(root);
27.     while(!que.empty())
28.     {
29.         int size=que.size();
30.         vector<int> vec;
31.         for(int i=0;i<size;i++)
32.         {
33.             Node* node=que.front();
34.             que.pop();
35.             vec.push_back(node->val);
36.             for(int j=0;j<node->children.size();j++)
37.             {
38.                 que.push(node->children[j]);
39.             }
40.         }
41.         res.push_back(vec);
42.     }
43.     return res;
44.     }
45. };

515在每个树行中找最大值

最大的int怎么写？INT32_MAX;过不了，初始化的num不够小。

初始化：不要num=-1*INT32_MAX;要：num=INT_MIN.

可能是因为这个：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     vector<int> largestValues(TreeNode* root) {
15.         vector<int> res;
16.         queue<TreeNode*> que;
17.         if(root!=nullptr) que.push(root);
18.         while(!que.empty())
19.         {
20.             int num=INT_MIN;
21.             int size=que.size();
22.             for(int i=0;i<size;i++)
23.             {
24.                 TreeNode* node=que.front();
25.                 que.pop();
26.                 num=max(num,node->val);
27.                 if(node->left) que.push(node->left);
28.                 if(node->right) que.push(node->right);
29.             }
30.             res.push_back(num);
31.         }
32.         return res;
33.     }
34. };

116填充每个节点的下一个右侧节点指针

怎么写，他要返回什么，怎么把next这个信息穿回去呢？

接上，为什么对node=que.front操作,return root就是答案？把root、node当做同一个东西就好。

思路（来自代码随想录）：

本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

1. /*
2. // Definition for a Node.
3. class Node {
4. public:
5.     int val;
6.     Node* left;
7.     Node* right;
8.     Node* next;
10.     Node() : val(0), left(NULL), right(NULL), next(NULL) {}
12.     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
14.     Node(int _val, Node* _left, Node* _right, Node* _next)
15.         : val(_val), left(_left), right(_right), next(_next) {}
16. };
17. */
19. class Solution {
20. public:
21.     Node* connect(Node* root) {
22.         queue<Node*> que;
23.         if(root!=nullptr) que.push(root);
24.         while(!que.empty()) 
25.         {
26.             Node* nodepre;
27.             Node* node;
28.             int size=que.size();
29.             for(int i=0;i<size;i++)
30.             {
31.                 //i是节点的指针，所以这里用i来写if
32.                 if(i==0){
33.                     nodepre=que.front();
34.                     que.pop();
35.                     node=nodepre;//勿漏
36.                 }
37.                 else{
38.                     node=que.front();//更新node
39.                     que.pop();
40.                     nodepre->next=node;//key
41.                     //不要忘了更新nodepre,nodepre的作用：记录当前节点（node）的上一个节点
42.                     nodepre=nodepre->next;
43.                 }
44.                 if(node->left) que.push(node->left);
45.                 if(node->right) que.push(node->right);
46.             }
47.             nodepre->next=nullptr;
48.         }
49.         return root;
50.         
51.     }
52. };

117填充每个节点的下一个右侧节点指针II

只要彻底理解了116，那么会发现这题是完全相同的，就当二刷了：

1. /*
2. // Definition for a Node.
3. class Node {
4. public:
5.     int val;
6.     Node* left;
7.     Node* right;
8.     Node* next;
10.     Node() : val(0), left(NULL), right(NULL), next(NULL) {}
12.     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
14.     Node(int _val, Node* _left, Node* _right, Node* _next)
15.         : val(_val), left(_left), right(_right), next(_next) {}
16. };
17. */
19. class Solution {
20. public:
21.     Node* connect(Node* root) {
22.         queue<Node*> que;
23.         if(root!=nullptr) que.push(root);
24.         while(!que.empty())
25.         {
26.             int size=que.size();
27.             Node* nodepre;
28.             Node* node;
29.             for(int i=0;i<size;i++)
30.             {
31.                 if(i==0){
32.                     nodepre=que.front();
33.                     que.pop();
34.                     node=nodepre;
35.                 }
36.                 else{
37.                     node=que.front();
38.                     que.pop();
39.                     nodepre->next=node;
40.                     nodepre=nodepre->next;
41.                 }
42.                 if(node->left) que.push(node->left);
43.                 if(node->right) que.push(node->right);
44.             }
45.             nodepre->next=nullptr;
46.         }
47.         return root;
48.     }
49. };

104二叉树的最大深度

简单：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     int maxDepth(TreeNode* root) {
15.         queue<TreeNode*> que;
16.         if(root!=nullptr) que.push(root);
17.         int res=0;
18.         while(!que.empty())
19.         {
20.             int size=que.size();
21.             for(int i=0;i<size;i++)
22.             {
23.                 TreeNode* node=que.front();
24.                 que.pop();
25.                 if(node->left) que.push(node->left);
26.                 if(node->right) que.push(node->right);
27.             }
28.             res++;
29.         }
30.         return res;
31.     }
32. };

111二叉树的最小深度

暂时没思路。再想想：左右孩子都为空，则说明到了最低点。

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     int minDepth(TreeNode* root) {
15.         queue<TreeNode*> que;
16.         int depth=0;
17.         if(root!=nullptr) que.push(root);
18.         while(!que.empty())
19.         {
20.             depth++;
21.             int size=que.size();
22.             for(int i=0;i<size;i++)
23.             {
24.                 TreeNode* node=que.front();
25.                 que.pop();
26.                 if(node->left) que.push(node->left);
27.                 if(node->right) que.push(node->right);
28.                 if(node->left==nullptr && node->right==nullptr) return depth;
29.             }
30.         }
31.         return depth;
32.     }
33. };

226翻转二叉树

交换指针竟然可以直接用swap来做。

前序版本：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     TreeNode* invertT(TreeNode* root)
15.     {
16.         if(root==nullptr) return root;
17.         swap(root->left,root->right);
18.         if(root->left) invertT(root->left);
19.         if(root->right) invertT(root->right);
20.         return root;
21.     }
22.     TreeNode* invertTree(TreeNode* root) {
23.         return invertT(root);
24.     }
25. };

后序版本：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     TreeNode* invertT(TreeNode* root)
15.     {
16.         if(root==nullptr) return root;
17.         if(root->left) invertT(root->left);
18.         if(root->right) invertT(root->right);
19.         swap(root->left,root->right);
20.         return root;
21.     }
22.     TreeNode* invertTree(TreeNode* root) {
23.         return invertT(root);
24.     }
25. };

试试前序遍历的迭代法：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     TreeNode* invertTree(TreeNode* root) {
15.         stack<TreeNode*> stk;
16.         if(root!=nullptr) stk.push(root);
17.         while(!stk.empty())
18.         {
19.             TreeNode* node=stk.top();
20.             stk.pop();
21.             swap(node->left,node->right);
22.             if(node->left) stk.push(node->left);
23.             if(node->right) stk.push(node->right);
24.         }
25.         return root;
26.     }
27. };

101对称二叉树

需要收集孩子的信息，并向上一级（某个根节点）返回这些信息时候，用后序遍历。

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     bool compare(TreeNode* left,TreeNode* right)
15.     {
16.         if(left==nullptr&&right==nullptr) return true;
17.         else if(left==nullptr&&right!=nullptr) return false;
18.         else if(left!=nullptr&&right==nullptr) return false;
19.         else if(left->val!=right->val) return false;
20.         // 此时就是：左右节点都不为空，且数值相同的情况.这时候才可以接着往下走，递归
21.         // 此时才做递归，做下一层的判断
22.         //不接着写else if了
23.         bool outside=compare(left->left,right->right);
24.         bool inside=compare(left->right,right->left);
25.         bool res=outside&&inside;
26.         return res;
27.         
28.     }
29.     bool isSymmetric(TreeNode* root) {
30.         return compare(root->left,root->right);
31.     }
32. };

对称二叉树的推荐题目：

100相同的树

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     bool iscom(TreeNode* p,TreeNode*q)
15.     {
16.         if(p==nullptr&&q==nullptr) return true;
17.         else if(p!=nullptr&&q==nullptr) return false;
18.         else if(p==nullptr&&q!=nullptr) return false;
19.         else if(p->val!=q->val) return false;
20.         bool o=iscom(p->left,q->left);
21.         bool i=iscom(p->right,q->right);
22.         bool res=i&&o;
23.         return res;
24.     }
25.     bool isSameTree(TreeNode* p, TreeNode* q) {
26.     return iscom(p,q);
27.     }
28. };

572另一棵树的子树

怎么下手呢？

力扣官方解法：深度优先搜索暴力匹配。

判断t是否和树s的任意子树相等。即：

判断s的每个子节点是否和t相等。3个条件，与的关系：

• 当前两个树的根节点的值是否相等
• 并且，s的左子树和t的左子树是否相等
• 并且，s的右子树和t的右子树是否相等

判断t是否为s的子树的三个条件，是或的关系：

• 当前两棵树相等
• 或者，t是s的左子树
• 或者，t是s的右子树

图片来自力扣官方题解

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     //dfs搜到之后，开始检查两个子树是否相等
15.     bool check(TreeNode*o,TreeNode*t)
16.     {
17.         if(o==nullptr&&t==nullptr) return true;
18.         if((o!=nullptr&&t==nullptr)||(o==nullptr&&t!=nullptr)||(o->val!=t->val)) return false;
19.         return (check(o->left,t->left) &&check(o->right,t->right));
20.     }
21.     //搜哪个是大子树里相等子树的根节点
22.     bool dfs(TreeNode* o,TreeNode* t)
23.     {
24.         if(o==nullptr) return false;
25.         //下一句一定要注意，是先o,t；前序遍历。注意逻辑，对当前遍历节点用check，需要递归时候，调用的是dfs
26.         return check(o,t)||dfs(o->left,t) ||dfs(o->right,t);
27.     }
28.     bool isSubtree(TreeNode* root, TreeNode* subRoot) {
29.         return dfs(root,subRoot);
30.     }
31. };

结束！明天早起，注意效率。