终于熬到了春节假~~有些手感了
深度与高度
深度是从根结点到叶结点的距离；高度是从叶结点到根结点的距离。
深度从上往下（根为1）；高度从下往上（叶为1）。
二叉树最大深度
leetcode：104. 二叉树的最大深度
后序递归法
思路
复杂度分析
时间复杂度：O(N)。遍历了一遍。
空间复杂度：和层数有关。平衡时O(logN)，不平衡时O(N)。
注意点
略
代码实现
/**
* 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 getMaxDepth(TreeNode* node){
if(node == NULL) return 0;
int LMD = getMaxDepth(node->left);
int RMD = getMaxDepth(node->right);
return 1 + (LMD > RMD ? LMD : RMD);
}
int maxDepth(TreeNode* root) {
return getMaxDepth(root);
}
};
N叉树最大深度
leetcode：559. N 叉树的最大深度
后序递归法
思路
还是后序遍历，只不过左右节点处理变为了对子节点数组children处理。
复杂度分析
时间复杂度：O(N)。遍历。
空间复杂度：递归遍历相通：平衡时O(logN)，不平衡时O(N)。
注意点
略
代码实现
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
int getMaxDepth(Node* node){
if(node == NULL) return 0;
int maxDepth = 0;
// 对于每一个child递归
for(int i = 0;i < node->children.size();i++){
int temp = getMaxDepth(node->children[i]);
maxDepth = temp > maxDepth ? temp : maxDepth;
}
return maxDepth + 1;
}
int maxDepth(Node* root) {
return getMaxDepth(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 getMinDepth(TreeNode* node){
if(node == NULL) return 0;
int LMD = getMinDepth(node->left);
int RMD = getMinDepth(node->right);
if(node->left == NULL && node->right != NULL){
return 1 + RMD;
}
if(node->left != NULL && node->right == NULL){
return 1 + LMD;
}
return 1 + ( LMD < RMD ? LMD : RMD );
}
int minDepth(TreeNode* root) {
return getMinDepth(root);
}
};
完全二叉树的节点个数
leetcode：222. 完全二叉树的节点个数
后序递归法
思路
节点遍历一遍，后序遍历。
复杂度分析
时间复杂度：O(N)
空间复杂度：最不平衡时O(N)，平衡时O(logN)。
注意点
略
代码实现
/**
* 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 preTraverse(TreeNode* node){
if(node == NULL) return 0;
// 先分支
int lcount = preTraverse(node->left);
int rcount = preTraverse(node->right);
// 再中间
return lcount + rcount + 1;
}
int countNodes(TreeNode* root) {
return preTraverse(root);
}
};
层序迭代法
思路
层序遍历一遍。
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(N)。最平衡时最后一层可能有大约N/2个节点。但极不平衡时空间复杂度很低。
注意点
略
代码实现
/**
* 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 countNodes(TreeNode* root) {
queue<TreeNode*> que;
if(root != NULL) que.push(root);
int count = 0;
while(!que.empty()){
int size = que.size();
while(size--){
TreeNode* node = que.front(); que.pop();
count++;
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
}
return count;
}
};
探测剪枝递归法
思路
满二叉树的节点数为2^(Depth) - 1
利用完全二叉树特性，在完全二叉树基础上，探测子树最左侧一条和最右侧一条深度是否相等，判断子树是否为满二叉树。如果是，则向上返回计算出的节点数。
复杂度分析
时间复杂度：不明确，小于O(N)，大于O(logN)。
空间复杂度：O(logN)。因为是完全二叉树，层数为logN级。
注意点
- 位运算
1 << N，相当于2^N。或者想用2 << N时，要把N - 1。 - 满二叉树节点数
N = 2^h - 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 countNodes(TreeNode* node) {
if(node == NULL) return 0;
TreeNode* left = node->left;
TreeNode* right = node->right;
int leftDepth = 1;
int rightDepth = 1;
while(left){
left = left->left;
leftDepth++;
}
while(right){
right = right->right;
rightDepth++;
}
if(leftDepth == rightDepth)
return (1 << leftDepth) - 1;
// 节点数 = 2^层数 - 1
// 1 << N 就是2^N （2的N次方）
return countNodes(node->left) + countNodes(node->right) + 1;
}
};