LeetCode：二叉树的属性（13道经典题目）
本文带来与二叉树的属性有关的经典题目，主要实现是C++。
给你一个二叉树的根节点 root ， 检查它是否轴对称。
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，也就是说我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
return compare(root->left, root->right);
}
bool compare(TreeNode* left, TreeNode* right) { // 后序遍历
// 排除空节点的情况
if (left == nullptr && right != nullptr) return false;
else if (left != nullptr && right == nullptr) return false;
else if (left == nullptr && right == nullptr) return true;
// 排除了空节点，再排除数值不相同的情况
else if (left->val != right->val) return false;
// 单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况
bool outside = compare(left->left, right->right);
bool inside = compare(left->right, right->left);
return outside && inside;
}
};
这里可以使用队列来比较两个树（根节点的左右子树）是否相互翻转。
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
queue<TreeNode*> que;
que.push(root->left);
que.push(root->right);
while (!que.empty()) {
TreeNode* leftNode = que.front(); que.pop();
TreeNode* rightNode = que.front(); que.pop();
if (!leftNode && !rightNode) continue;
if (!leftNode || !rightNode || leftNode->val != rightNode->val) {
return false;
}
que.push(leftNode->left);
que.push(rightNode->right);
que.push(leftNode->right);
que.push(rightNode->left);
}
return true;
}
};
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
跟 101. 对称二叉树 基本一样。
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) return true;
else if (!p || !q || p->val != q->val) return false;
else {
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
}
};
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) return true;
if (!p || !q) return false;
queue<TreeNode*> que;
que.push(p);
que.push(q);
while (!que.empty()) {
TreeNode* left = que.front(); que.pop();
TreeNode* right = que.front(); que.pop();
if (!left && !right) continue;
if (!left || !right || left->val != right->val) return false;
que.push(left->left);
que.push(right->left);
que.push(left->right);
que.push(right->right);
}
return true;
}
};
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
一个树是另一个树的子树 则
- 要么这两个树相等
- 要么这个树是左树的子树
- 要么这个树是右树的子树
class Solution {
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (root == nullptr && subRoot == nullptr) return true;
if (root == nullptr && subRoot != nullptr) return false;
return compare(root, subRoot)
|| isSubtree(root->left, subRoot)
|| isSubtree(root->right, subRoot);
}
bool compare(TreeNode* left, TreeNode* right) {
if (!left && !right) return true;
else if (!left || !right || left->val != right->val) return false;
return compare(left->left, right->left) && compare(left->right, right->right);
}
};
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
使用前序求的就是深度，使用后序求的是高度。根节点的高度就是二叉树的最大深度。
class Solution {
public:
int maxDepth(TreeNode* root) {
return getDepth(root);
}
int getDepth(TreeNode* root) {
if (root == nullptr) return 0;
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return 1 + max(leftDepth, rightDepth);
}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
result = 0;
if (root == nullptr) return result;
getDepth(root, 1);
return result;
}
void getDepth(TreeNode* node, int depth) {
result = depth > result ? depth : result; // 中
if (node->left == nullptr && node->right == nullptr) {
return;
}
if (node->left) {
getDepth(node->left, depth + 1);
}
if (node->right) {
getDepth(node->right, depth + 1);
}
return;
}
int result = 0;
};
使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。代码见：104. 二叉树的最大深度 层次遍历迭代法
给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔。
class Solution {
public:
int maxDepth(Node* root) {
return getDepth(root);
}
int getDepth(Node* node) {
int depth = 0;
if (node == nullptr) return 0;
/*for (vector<Node*>::iterator it = node->children.begin(); it != node->children.end(); it++) {
depth = max(getDepth(*it), depth);
}*/
for (int i = 0; i < node->children.size(); i++) {
depth = max(getDepth(node->children[i]), depth);
}
return depth + 1;
}
};
class Solution {
public:
int maxDepth(Node* root) {
if (root == nullptr) return 0;
queue<Node*> que;
int depth = 0;
que.push(root);
while (!que.empty()) {
int size = que.size();
depth++;
for (int i = 0; i < size; i++) {
Node* node = que.front();
que.pop();
for (int j = 0; j < node->children.size(); j++) {
if (node->children[j]) {
que.push(node->children[j]);
}
}
}
}
return depth;
}
};
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
class Solution {
public:
int minDepth(TreeNode* node) {
if (node == nullptr) return 0;
if (node->left && !node->right) { // 当一个左子树为空，右不为空，这时并不是最低点
return 1 + minDepth(node->left);
}
if (!node->left && node->right) { // 当一个右子树为空，左不为空，这时并不是最低点
return 1 + minDepth(node->right);
}
return 1 + min(minDepth(node->left), minDepth(node->right));
}
};
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
把完全二叉树当作普通二叉树来做：
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
int leftNum = countNodes(root->left);
int rightNum = countNodes(root->right);
return 1 + leftNum + rightNum;
}
};
层序遍历：
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> que;
que.push(root);
int num = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
num++;
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return num;
}
};
题目中给了完全二叉树，那么可以用完全二叉树的性质来做题。
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
- 对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
- 对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftHeight = 0, rightHeight = 0; // 这里初始为0是有目的的，为了下面求指数方便
while (left) { // 求左子树深度
left = left->left;
leftHeight++;
}
while (right) { // 求右子树深度
right = right->right;
rightHeight++;
}
if (leftHeight == rightHeight) {
return (2 << leftHeight) - 1; // 注意(2<<1) 相当于2^2，所以leftHeight初始为0
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）
class Solution {
public:
bool isBalanced(TreeNode* root) {
return getDepth(root) == -1 ? false : true;
}
// -1表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度
int getDepth(TreeNode* node) {
if (node == nullptr) return 0;
int leftHeight = getDepth(node->left);
if (leftHeight == -1) return -1;
int rightHeight = getDepth(node->right);
if (rightHeight == -1) return -1;
return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
}
};
通过栈模拟的后序遍历找每一个节点的高度
class Solution {
public:
bool isBalanced(TreeNode* root) {
stack<TreeNode*> st;
if (root == nullptr) return true;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (abs(getDepth(node->left) - getDepth(node->right)) > 1) {
return false;
}
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
return true;
}
// cur节点的最大深度，就是cur的高度
int getDepth(TreeNode* cur) {
stack<TreeNode*> st;
if (cur != nullptr) st.push(cur);
int depth = 0;
int result = 0;
while (!st.empty()) {
TreeNode* node = st.top();
if (node != nullptr) {
st.pop();
st.push(node);
st.push(nullptr);
depth++;
if (node->left) st.push(node->left);
if (node->right) st.push(node->right);
}
else {
st.pop();
node = st.top();
st.pop();
depth--;
}
result = result > depth ? result : depth;
}
return result;
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
