101. 对称二叉树
对称就是左子树和右子树里侧和外侧的元素是否相等，因为要比较子节点，所以应该采用后序遍历，并且左右子树的左右子节点的遍历顺序应该是反的，比如一个树是左右中，另一个就应该是右左中。
递归法
确定递归终止条件：
要处理节点为空的各种情况
节点为空：
- 左节点为空，右节点不空，不对称，返回false
- 左不空，右空，不对称，返回false
- 左右都空，对称，返回true
节点不为空：
- 数值相同，返回true
- 数值不同，返回false
class Solution {public:bool compare(TreeNode* left, TreeNode* right) {if (left == nullptr && right == nullptr) // 两个节点都为空，返回truereturn true;if (left == nullptr || right == nullptr || left->val != right->val) // 一空一不空或者数值不相等，返回falsereturn false;return compare(left->left, right->right) && compare(left->right, right->left);}bool isSymmetric(TreeNode* root) {if (root == nullptr) return true;return compare(root->left, root->right);}};
迭代法
这里我们可以使用队列来比较两个树（根节点的左右子树）是否相互翻转，（注意这不是层序遍历）
使用队列
/**
* 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:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
queue<TreeNode*> que;
que.push(root->left);
que.push(root->right);
while(!que.empty()) {
TreeNode* lnode = que.front();
que.pop();
TreeNode* rnode = que.front();
que.pop();
// 与递归法的逻辑相同
if (!lnode && !rnode) continue; //左右都空，下一轮
if (!lnode || !rnode || lnode->val != rnode->val) // 有一个不空或者数值不等，不对称
return false;
que.push(lnode->left);
que.push(rnode->right);
que.push(lnode->right);
que.push(rnode->left);
}
return true;
}
};
使用栈
其实迭代法就是把要比较的两个元素成对放入容器然后再比较，因此使用栈也可，将队列改成栈其他的代码不用动
/**
* 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:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
stack<TreeNode*> stk;
stk.push(root->left);
stk.push(root->right);
while(!stk.empty()) {
TreeNode* lnode = stk.top();
stk.pop();
TreeNode* rnode = stk.top();
stk.pop();
// 与递归法的逻辑相同
if (!lnode && !rnode) continue; //左右都空，下一轮
if (!lnode || !rnode || lnode->val != rnode->val) // 有一个不空或者数值不等，不对称
return false;
stk.push(lnode->left);
stk.push(rnode->right);
stk.push(lnode->right);
stk.push(rnode->left);
}
return true;
}
};
100. 相同的树
这道题和对称二叉树思想是一样的只不过那个是对比内侧和外侧的节点是否相等，这个是比较两个树同一位置的节点是否相同。
同样的要处理存在节点为空的情况
递归法
- 确定递归函数的参数和返回值
比较两树的节点是否相等，所以参数是两个节点，返回值为bool
- 确定终止条件
- 两节点都空，返回true
- 只有一个空或者数值不相等，返回false
- 数值相同，处理接下来的节点
- 单层递归逻辑
如果两节点数值相同，那么递归判断左子树和右子树
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
return compare(p, q);
}
bool compare(TreeNode* first, TreeNode* second) {
if (!first && !second) return true;
if (!first || !second || first->val != second->val) return false;
return compare(first->left, second->left) && compare(first->right, second->right);
}
};
或者只写一个函数
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if (!p || !q || p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
迭代法
和递归法一样的思路，将两个节点放入容器中，然后取出来进行比较
这里选择队列作为容器
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
queue<TreeNode*> que;
que.push(p);
que.push(q);
while (!que.empty()) {
TreeNode* node1 = que.front(); que.pop();
TreeNode* node2 = que.front(); que.pop();
if (!node1 && !node2) continue;
if (!node1 || !node2 || node1->val != node2->val)
return false;
que.push(node1->left);
que.push(node2->left);
que.push(node1->right);
que.push(node2->right);
}
return true;
}
};
572. 另一棵树的子树
这道题可以用相同的树的解法，在主树的每个节点判断树是否与子树相等，如果存在相等的，那么就包含
class Solution {
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
//处理存在空节点的情况
if (!root && !subRoot)
return true;
if (!root || !subRoot)
return false;
//节点不空，当前节点和子树相同，或者左子树与子树相同，或者右子树和子树相同，三者有一个相同即存在
return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if (!p || !q || p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
226. 翻转二叉树
递归法
后序遍历
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return root;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};
先序遍历
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return root;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
迭代法
先序遍历
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return root;
stack<TreeNode*> st;
TreeNode* cur = root;
st.push(cur);
while (!st.empty()) {
cur = st.top();
st.pop();
swap(cur->left, cur->right);
if (cur->right) st.push(cur->right);
if (cur->left) st.push(cur->left);
}
return root;
}
};
广度优先
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
swap(node->left, node->right); // 节点处理
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return root;
}
};
若有收获，就点个赞吧
0 人点赞
