101. 对称二叉树
描述
示例
二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
说明
- 如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
思路
- 类比两个相等的二叉树，两个树镜像对称，即左树的左子树和右树的右子树相等、左树的右子树和右树的左子树相等。
- 迭代版本，则利用一个栈来代替递归的作用。
(参考地址)
class Solution_101_01 {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return isMirror(root->left, root->right);
}
bool isMirror(TreeNode* root1, TreeNode* root2) {
// If both trees are emptu, then they are mirror images
if (root1 == NULL && root2 == NULL) return true;
// For two trees to be mirror images, the following three
// conditions must be true
// 1 - Their root node's key must be same
// 2 - left subtree of left tree and right subtree
// of right tree have to be mirror images
// 3 - right subtree of left tree and left subtree
// of right tree have to be mirror images
if (root1 && root2 && root1->val == root2->val)
return isMirror(root1->left, root2->right) &&
isMirror(root1->right, root2->left);
// if neither of above conditions is true then root1
// and root2 are not mirror images
return false;
}
};
class Solution_101_02 {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return isMirror(root->left, root->right);
}
bool isMirror(TreeNode* root1, TreeNode* root2) {
stack<TreeNode*> s;
s.push(root1);
s.push(root2);
while (!s.empty()) {
TreeNode* tmp1 = s.top();
s.pop();
TreeNode* tmp2 = s.top();
s.pop();
if (!tmp1 && !tmp2) continue;
if (!tmp1 || !tmp2 || tmp1->val != tmp2->val) return false;
s.push(tmp1->left);
s.push(tmp2->right);
s.push(tmp1->right);
s.push(tmp2->left);
}
return true;
}
};
102. 二叉树的层次遍历
描述
- 给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。
示例
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
思路
- 利用队列实现层次遍历，两个队列交替使用，保存“层”的信息。
- 优化上述解法中利用两个队列来解决“层”的问题。每次遍历时，先取元素的个数，相当于是获得了改成元素的个数，再遍历。
class Solution_102_01 {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == NULL) return vector<vector<int>>();
vector<vector<int>> res;
queue<TreeNode*> q1, q2;
q1.push(root);
while (!q1.empty() && !q2.empty()) {
queue<TreeNode*>& curQ = q1.empty() ? q2 : q1;
queue<TreeNode*>& bakQ = curQ == q1 ? q2 : q1;
vector<int> tmp;
while (!curQ.empty()) {
TreeNode* node = curQ.front();
curQ.pop();
tmp.push_back(node->val);
if (node->left) bakQ.push(node->left);
if (node->right) bakQ.push(node->right);
}
res.push_back(tmp);
}
return res;
}
};
class Solution_102_02 {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root) return {};
vector<vector<int>> res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int size = q.size();
vector<int> level;
while(size--){
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.push_back(level);
}
return res;
}
};
