代码随想录算法训练营第36期DAY19

DAY19

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.         int md=0;
17.         if(root!=nullptr) que.push(root);
18.         while(!que.empty())
19.         {
20.             md++;
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.             }
29.         }
30.         return md;
31.     }
32. };

递归法：

核心：

1. class Solution {
2. public:
3.     int getdepth(TreeNode* node) {
4.         if (node == NULL) return 0;
5.         int leftdepth = getdepth(node->left);       // 左
6.         int rightdepth = getdepth(node->right);     // 右
7.         int depth = 1 + max(leftdepth, rightdepth); // 中
8.         return depth;
9.     }
10.     int maxDepth(TreeNode* root) {
11.         return getdepth(root);
12.     }
13. };

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 geth(TreeNode* root)
15.     {
16.         if(root==nullptr) return 0;//叶子之下的，高度为0
17.         return 1+max(geth(root->left),geth(root->right));
18.     }
19.     int maxDepth(TreeNode* root) {
20.         return geth(root);
21.     }
22. };

559 n叉树的最大深度

递归，非递归写过了，不写了：

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.     int maxDepth(Node* root) {
24.     if(root==nullptr) return 0;
25.     int depth=0;
26.     for(int i=0;i<root->children.size();i++)
27.     {
28.         depth=max(depth,maxDepth(root->children[i]));
29.     }
30.     return depth+1;
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.         int ld=0;
16.         queue<TreeNode*> que;
17.         if(root!=nullptr) que.push(root);
18.         while(!que.empty())
19.         {
20.             int size=que.size();
21.             ld++;
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 ld;
29.             }
30.         }
31.         return ld;
32.     }
33. };

递归法：

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.     //后序遍历
15.     int getd(TreeNode* root)
16.     {
17.         if(root==nullptr) return 0;
18.         int leftd=getd(root->left);
19.         int rightd=getd(root->right);
20.         //中
21.         if(root->left==nullptr&&root->right!=nullptr) return 1+rightd;
22.         if(root->left!=nullptr&&root->right==nullptr) return 1+leftd;
23.         return 1+min(leftd,rightd);
24.     }
25.     int minDepth(TreeNode* root) {
26.         return getd(root);
27.     }
28. };

222完全二叉树的节点个数

层序遍历法：

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 countNodes(TreeNode* root) {
15.         int res=0;
16.         queue<TreeNode*> que;
17.         if(root!=nullptr) que.push(root);
18.         while(!que.empty())
19.         {
20.             int size=que.size();
21.             res+=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.             }
29.         }
30.         return res;
31.     }
32. };

递归法：

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 countNodes(TreeNode* root) {
15.         if(root==nullptr) return 0;
16.         return 1+countNodes(root->left)+countNodes(root->right);
17.     }
18. };

从完全二叉树的定义入手：

来自代码随想录：

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，就说明是满二叉树。

代码；

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 fulltree(TreeNode* root)
15.     {
16.         if(root==nullptr) return 0;
17.         TreeNode* left=root->left;
18.         TreeNode* right=root->right;
19.         int leftdepth=0,rightdepth=0;
20.         //求左子树深度
21.         while(left)
22.         {
23.             left=left->left;
24.             leftdepth++;
25.         }
26.         while(right)
27.         {
28.             right=right->right;
29.             rightdepth++;
30.         }
31.         if(leftdepth==rightdepth) return (2<<leftdepth)-1;
32.         //如果没找到满二叉树，就继续向左向右递归（后序遍历）+1表示中节点
33.         return fulltree(root->left)+fulltree(root->right)+1;
34.       }
35.     int countNodes(TreeNode* root) {
36.         return fulltree(root);
37.     }
38. };

总结

深度：任意节点与根节点的距离（从1开始，也就是：根节点深度是1）；用前序遍历来求，

高度：任意节点到叶子节点的距离。用后序遍历来求。（找叶子：要把孩子的信息返回给节点，所以用后序遍历）。根节点的高度就是二叉树的最大深度。

记忆：深根（前序） 高叶（后序）

写前序是比较麻烦的。一般写后序了。