摘要
- 二叉树的深度是从根节点出发，到最远的叶节点的最长路径上的节点数
- 二叉树的高度是从最远叶节点出发，到根节点的最长路径上的节点数
- 完全二叉树可以的节点个数和树的高度与深度有明显的规律
LeetCode104 二叉树的深度
- 关键概念
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
- 从0开始为边的条数，从1开始为节点数
- 层序遍历实现求二叉树的深度
class Solution {
public:
int maxDepth(TreeNode* root) {
queue<TreeNode*> que;
if (root) que.push(root);
int res = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
res++;
}
return res;
}
};
- 后序遍历实现求二叉树的深度，
- 实际上是逐步求每个节点的高度，从而最后求出根节点的高度。而根节点的高度正好是二叉树的深度。
class Solution {
public:
int depthOf(TreeNode* node) {
if (!node) return 0;
int leftDepth = depthOf(node->left);
int rightDepth = depthOf(node->right);
int depth = 1 + max(leftDepth, rightDepth);
return depth;
}
int maxDepth(TreeNode* root) {
return depthOf(root);
}
};
LeetCode559 N叉树的最大深度
- 求树的深度，还是层序遍历更容易扩展到N叉树
class Solution {
public:
int maxDepth(Node* root) {
queue<Node*> que;
if (root) que.push(root);
int depth = 0;
while (!que.empty()) {
int size = que.size();
depth++;
for (int i = 0; i < size; i++) {
for (auto& iter : que.front()->children) {
if (iter) que.push(iter);
}
que.pop();
}
}
return depth;
}
};
LeetCode111 二叉树的最小深度
-
二叉树的最小深度是根节点到最近叶节点的经过节点数。
- 由于我们在递归终止条件中定义空节点的返回值为
0（空节点对应一棵空的子树，高度或者深度自然是零） - 这会直接影响左右子树的最小深度比较。空节点并不是子树或者叶节点，所以需要我们手动排除空节点，只有左右子树都存在时比较左右子树的深度才有意义。
- 由于我们在递归终止条件中定义空节点的返回值为
后序遍历的代码实现
class Solution {
public:
int minDepthOf(TreeNode* node) {
if (!node) {
return 0;
}
int leftMinDepth = minDepthOf(node->left);
int rightMinDepth = minDepthOf(node->right);
int minDepth = 1;
if (node->left && !node->right) minDepth += leftMinDepth;
else if (!node->left && node->right) minDepth += rightMinDepth;
else minDepth += min(leftMinDepth, rightMinDepth);
return minDepth;
}
int minDepth(TreeNode* root) {
return minDepthOf(root);
}
};
- 层序遍历，在这道题中，层序遍历的代码依然更加直观、更加容易理解。
class Solution {
public:
int minDepth(TreeNode* root) {
queue<TreeNode*> que;
if (root) que.push(root);
int res = 0;
while (!que.empty()) {
int size = que.size();
res++;
for (int i = 0; i < size; i++) {
// 到达叶节点则直接返回当前深度
if (!que.front()->left && !que.front()->right) {
return res;
}
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
}
return res;
}
};
LeetCode222 完全二叉树的节点个数
-
关键概念
- 完美二叉树（Perfect Binary Tree），又称满二叉树（Full Binary Tree）：每层的节点数都达到最大值的二叉树就是完美二叉树。
- 这里我再查阅了一下国外的教材，Full Binary Tree还有完满二叉树的意思，完满二叉树指的是如果一个节点有子节点，则该节点一定既有左孩子又有右孩子。和题目无关，只是定义上的歧义，这里先不讨论。
- 完全二叉树（Complete Binary Tree），可以由完美二叉树定义，将完美二叉树按层序遍历的顺序，从最后一个节点向前逐个删除节点，得到的二叉树都是完全二叉树。
- 完全二叉树（Complete Binary Tree）：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第
h层，则该层包含1~ 2h个节点。
- 完美二叉树（Perfect Binary Tree），又称满二叉树（Full Binary Tree）：每层的节点数都达到最大值的二叉树就是完美二叉树。
-
利用完全二叉树的性质，可以减少计算完全二叉树的节点数需要访问的节点数。
- 虽然完全二叉树的节点数和层数之间的关系是不确定的，但完全二叉树的子树可能包含完美二叉树。
- 完美二叉树的节点个数和其层数是确定的，一个完美二叉树的层数为
k，则该完美二叉树拥有的节点数为2^k - 1。
-
所以，虽然完全二叉树不一定是完美二叉树，但可以继续判断它的子树是否完美二叉树，如果它的子树是完美二叉树，就可以通过该子树的深度算出子树的节点数。这样就能达到减少访问的节点数的目的。
- 递归函数的参数和返回值：判断当前子树是否为完美二叉树，如果为完美二叉树，则根据其深度计算节点个数，如果不为完美二叉树，则继续判断其左子树和右子树是否为完美二叉树。参数应为（子）树的根节点，返回值为节点数。
-
递归的终止条件：一是当前子树的根节点为
nullptr，空树返回值为0；而是当前子树为完美二叉树，计算出节点数后直接返回。 - 单层递归的逻辑：从当前节点出发，计算当前树的左子树的深度和右子树的深度。若左子树的深度和右子树相等，则当前树为完美二叉树，可以直接根据深度计算出节点个数；若当前树不为完美二叉树，则递归判断其左子树和右子树是否为完美二叉树。
递归实现
class Solution {
public:
int completeTreeNodes(TreeNode* node) {
if (!node) return 0;
TreeNode* left = node;
int leftDepth = 0;
while (left) {
left = left->left;
leftDepth++;
}
TreeNode* right = node;
int rightDepth = 0;
while (right) {
right = right->right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return pow(2, leftDepth) - 1;
}
else {
return completeTreeNodes(node->left) + completeTreeNodes(node->right) + 1;
}
}
int countNodes(TreeNode* root) {
return completeTreeNodes(root);
}
};
普通的后序遍历
int postorderCountNodes(TreeNode* node) {
if (!node) return 0;
return postorderCountNodes(node->left) + postorderCountNodes(node->right) + 1;
}
