C++刷剑指offer(面试题28. 对称的二叉树)【递归】

糖逗 · 发表于 2020-4-2 20:39:52

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由糖逗于 2020-5-8 18:04 编辑

题目描述：

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [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
 
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
 
限制：
0 <= 节点个数 <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

#include<iostream>
#include <malloc.h>
#include <vector>
#include <math.h>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(NULL), right(NULL){
}
};
TreeNode* CreateTree(vector<int> input){
TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
for(int i = 0; i < input.size(); i++){
res[i].val = input[i];
res[i].left = NULL;
res[i].right = NULL;
}
for(int i= 0; i < input.size(); i++){
if(2*i+1 < input.size()){
res[i].left = &res[2*i+1];
}
if(2*i+2 < input.size()){
res[i].right = &res[2*i+2];
}
}
return res;
}
void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
if(root == NULL) return;
int insert = left + (right - left) / 2;
res[depth][insert] = root->val;
middle(root->left, res, left, insert - 1, depth + 1);
middle(root->right, res, insert + 1, right, depth + 1);
}
int treeDepth(TreeNode* root){
if(root == NULL || root -> val == 0) return 0;
return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
}
void printTree(TreeNode* root) {
int depth = treeDepth(root);
int width = pow(2, depth) - 1;
vector<vector<int> > res(depth, vector<int>(width, 0));
middle(root, res, 0, width - 1, 0);
for(int i = 0; i < res.size(); i++){
for(int j = 0; j < res[i].size();j++){
if(res[i][j] == 0){
cout << " ";
}
else{
cout << res[i][j];
}
}
cout << endl;
}
cout << "------------------" << endl;
}
bool solution(TreeNode* right, TreeNode* left){
if(right == NULL && left != NULL) return false;
if(right != NULL && left == NULL) return false;
if(right == NULL && left == NULL) return true;
if(right -> val != left -> val) return false;
return solution(right -> left, left->right) && solution(left->left, right->right);
}
bool isSymmetric(TreeNode* root) {
if(root == NULL) return true;
return solution(root -> right, root -> left);
}
int main(void){
vector<int> input;
cout << "send numbers for the tree" << endl;
int number;
while(cin >> number){
input.push_back(number);
}
TreeNode* root = CreateTree(input);
printTree(root);
bool res = isSymmetric(root);
cout << res << endl;
return 0;
}

复制代码

注意事项：
1.解题思路如图1。
2.需要另外写一个函数做左右节点的判断。

糖逗 · 发表于 2020-4-2 20:40:26

核心代码：

bool solution(TreeNode* right, TreeNode* left){
if(right == NULL && left != NULL) return false;
if(right != NULL && left == NULL) return false;
if(right == NULL && left == NULL) return true;
if(right -> val != left -> val) return false;
return solution(right -> left, left->right) && solution(left->left, right->right);
}
bool isSymmetric(TreeNode* root) {
if(root == NULL) return true;
return solution(root -> right, root -> left);
}

复制代码

糖逗 · 发表于 2020-4-2 20:41:19

账号		自动登录	找回密码
密码			立即注册

[技术交流] C++刷剑指offer(面试题28. 对称的二叉树)【递归】

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐: