LeetCode:Minimum Depth of Binary Tree,Maximum Depth of Binary Tree

LeetCode:Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

算法1：dfs递归的求解

 1 class Solution {
 2 public:
 3     int minDepth(TreeNode *root) {
 4         // IMPORTANT: Please reset any member data you declared, as
 5         // the same Solution instance will be reused for each test case.
 6         if(root == NULL)return 0;
 7         int res = INT_MAX;
 8         dfs(root, 1, res);
 9         return res;
10     }
11     void dfs(TreeNode *root, int depth, int &res)
12     {
13         if(root->left == NULL && root->right == NULL && res > depth)
14             {res = depth; return;}
15         if(root->left)
16             dfs(root->left, depth+1, res);
17         if(root->right)
18             dfs(root->right, depth+1, res);
19     }
20 };

View Code

还有一种更直观的递归解法，分别求左右子树的最小深度，然后返回左右子树的最小深度中较小者+1

 1 class Solution {
 2 public:
 3     int minDepth(TreeNode *root) {
 4         if(root == NULL)return 0;
 5         int minleft = minDepth(root->left);
 6         int minright = minDepth(root->right);
 7         if(minleft == 0)
 8             return minright + 1;
 9         else if(minright == 0)
10             return minleft + 1;
11         else return min(minleft, minright) + 1;
12     }
13 };

算法2：层序遍历二叉树，找到最先遍历到的叶子的层数就是树的最小高度

 1 /**
 2  * Definition for binary tree
 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     int minDepth(TreeNode *root) {
13         // IMPORTANT: Please reset any member data you declared, as
14         // the same Solution instance will be reused for each test case.
15          //层序遍历，碰到第一个叶子节点就停止,NULL作为每一层节点的分割标志
16         if(root == NULL)return 0;
17         int res = 0;
18         queue<TreeNode*> Q;
19         Q.push(root);
20         Q.push(NULL);
21         while(Q.empty() == false)
22         {
23             TreeNode *p = Q.front();
24             Q.pop();
25             if(p != NULL)
26             {
27                 if(p->left)Q.push(p->left);
28                 if(p->right)Q.push(p->right);
29                 if(p->left == NULL && p->right == NULL)
30                 {
31                     res++;
32                     break;
33                 }
34             }
35             else 
36             {
37                 res++;
38                 if(Q.empty() == false)Q.push(NULL);
39             }
40         }
41         return res;
42     }
43 };

本文地址

LeetCode:Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

算法1：dfs递归求解

 1 /**
 2  * Definition for binary tree
 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     int maxDepth(TreeNode *root) {
13         // IMPORTANT: Please reset any member data you declared, as
14         // the same Solution instance will be reused for each test case.
15         if(root == NULL)return 0;
16         int res = INT_MIN;
17         dfs(root, 1, res);
18         return res;
19     }
20     void dfs(TreeNode *root, int depth, int &res)
21     {
22         if(root->left == NULL && root->right == NULL && res < depth)
23             {res = depth; return;}
24         if(root->left)
25             dfs(root->left, depth+1, res);
26         if(root->right)
27             dfs(root->right, depth+1, res);
28     }
29 };

View Code

同上一题

 1 class Solution {
 2 public:
 3     int maxDepth(TreeNode *root) {
 4         if(root == NULL)return 0;
 5         int maxleft = maxDepth(root->left);
 6         int maxright = maxDepth(root->right);
 7         if(maxleft == 0)
 8             return maxright + 1;
 9         else if(maxright == 0)
10             return maxleft + 1;
11         else return max(maxleft, maxright) + 1;
12     }
13 };

算法2：层序遍历，树的总层数就是树的最大高度

 1 /**
 2  * Definition for binary tree
 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     int maxDepth(TreeNode *root) {
13         // IMPORTANT: Please reset any member data you declared, as
14         // the same Solution instance will be reused for each test case.
15         //层序遍历计算树的层数即可,NULL作为每一层节点的分割标志
16         if(root == NULL)return 0;
17         int res = 0;
18         queue<TreeNode*> Q;
19         Q.push(root);
20         Q.push(NULL);
21         while(Q.empty() == false)
22         {
23             TreeNode *p = Q.front();
24             Q.pop();
25             if(p != NULL)
26             {
27                 if(p->left)Q.push(p->left);
28                 if(p->right)Q.push(p->right);
29             }
30             else 
31             {
32                 res++;
33                 if(Q.empty() == false)Q.push(NULL);
34             }
35         }
36         return res;
37     }
38 };