LeetCode 104. 二叉树的最大深度
题目:
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
思路：
对二叉树后序遍历，记录层数
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int gethight(TreeNode* pointer)
{
if(pointer==NULL)
{
return 0;
}
int leftnum=gethight(pointer->left);
int rightnum=gethight(pointer->right);
int depth=1+max(leftnum,rightnum);
return depth;
}
int maxDepth(TreeNode* root) {
int res=gethight(root);
return res;
}
};
LeetCode 111. 二叉树的最小深度
题目：
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
思路：
与上一道题目类似，把求最大换成求最小就行。需要注意的是根据题目要求，如果根节点的左右某一个子树不存在，最小深度不能认为是1。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int getmin(TreeNode* pointer)
{
if(pointer==NULL) return 0;
int leftnumber=getmin(pointer->left);
int rightnumber=getmin(pointer->right);
if(pointer->left==NULL && pointer->right!=NULL)
{
return 1+rightnumber;
}else if(pointer->left!=NULL && pointer->right==NULL)
{
return 1+leftnumber;
}
int depthmin=1+min(leftnumber,rightnumber);
return depthmin;
}
int minDepth(TreeNode* root) {
int res=getmin(root);
return res;
}
};
LeetCode 222. 完全二叉树的节点个数
题目：
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
思路：
一种方法是按照普通二叉树进行后序遍历，统计遍历的个数；另一种方法是结合二叉树的特性，对于满二叉树，其所有节点的数目是2^n-1，所以如果完全二叉树中有满二叉子树，那么其中的节点都不需要遍历统计。判断满二叉只需要判断最左边的深度和最右边的深度是否一致，一致则说明是满二叉树，否则就不是。
代码：
(思路一)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int getnum(TreeNode* pointer)
{
if(pointer==NULL) return 0;
int leftnum=getnum(pointer->left);
int rightnum=getnum(pointer->right);
int num=leftnum+rightnum+1;
return num;
}
int countNodes(TreeNode* root) {
return getnum(root);
}
};
（思路二）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int getnum(TreeNode* pointer)
{
if(pointer==NULL) return 0;
TreeNode* leftpointer=pointer->left;
TreeNode* rightpointer=pointer->right;
int leftnum=0,rightnum=0;
while(leftpointer)
{
leftpointer=leftpointer->left;
leftnum++;
}
while(rightpointer)
{
rightpointer=rightpointer->right;
rightnum++;
}
if(leftnum==rightnum)return (2<<leftnum)-1;
int leftsum=getnum(pointer->left);
int rightsum=getnum(pointer->right);
int sum=leftsum+rightsum+1;
return sum;
}
int countNodes(TreeNode* root) {
return getnum(root);
}
};
