對稱二叉樹
題目描述：
給定一個二叉樹，檢查它是否是鏡像對稱的，
例如，二叉樹 [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
進階：
你可以運用遞回和迭代兩種方法解決這個問題嗎？
方法一：遞回（dfs）
//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 check(TreeNode* node1,TreeNode* node2){
if(node1==nullptr && node2==nullptr) return true;
if((node1==nullptr)^(node2==nullptr)) return false;
if(node1->val!=node2->val) return false;
return check(node1->left,node2->right) && check(node1->right,node2->left);
}
bool isSymmetric(TreeNode* root) {
if(root==nullptr) return true;
if(root->left==nullptr && root->right==nullptr) return true;
return check(root->left,root->right);
}
};
方法二：迭代（利用佇列，bfs）
//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==nullptr || (root->left==nullptr && root->right==nullptr)) return true;
if((root->left==nullptr)^(root->right==nullptr)) return false;
queue<TreeNode*> que;
que.push(root->left);
que.push(root->right);
while(!que.empty()){
auto node1=que.front();
que.pop();
auto node2=que.front();
que.pop();
if(node1->val!=node2->val) return false;
if((node1->left==nullptr)^(node2->right==nullptr)) return false;
if((node1->right==nullptr)^(node2->left==nullptr)) return false;
if(node1->left!=nullptr) que.push(node1->left);
if(node2->right!=nullptr) que.push(node2->right);
if(node1->right!=nullptr) que.push(node1->right);
if(node2->left!=nullptr) que.push(node2->left);
}
return true;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/350834.html
標籤：其他
下一篇：429. N 叉樹的層序遍歷