手撕代码锻炼 101. 对称二叉树
作者:
liweidong
,
2023-03-20 10:14:01
,
所有人可见
,
阅读 229
/*
* DFS
*/
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int val;
Node *left;
Node *right;
Node(int x) : val(x), left(nullptr), right(nullptr) {}
};
/*
* 每次比较两棵子树
*
*/
bool dfs(Node *l, Node *r) {
// 两个节点都为空
if (!l && !r) return true;
// 其中一个节点为空
if (!l || !r) return false;
// 值不相同
if (l->val != r->val) return false;
// 值相同
return dfs(l->left, r->right) && dfs(l->right, r->left);
}
bool isSymmetry(Node *root) {
return dfs(root->left, root->right);
}
Node *buildTree(vector<int> &nums) {
// 为非空节点分配内存
int n = nums.size();
vector<Node *> nodes(n);
for (int i = 0; i < n; i++) {
if (nums[i] != INT_MAX) nodes[i] = new Node(nums[i]);
}
// 为非空节点关联左右节点
for (int i = 0; i < n; i++) {
if (nodes[i]) {
if (2 * i + 1 < n) nodes[i]->left = nodes[2 * i + 1];
if (2 * i + 2 < n) nodes[i]->right = nodes[2 * i + 2];
}
}
return nodes[0];
}
int main() {
// 建立二叉树
vector<int> nums{1, 2, 2, INT_MAX, 3, INT_MAX, 3};
Node *root = buildTree(nums);
cout << isSymmetry(root) << endl;
return 0;
}