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

糖逗

题目描述：

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [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.需要另外写一个函数做左右节点的判断。

糖逗

核心代码：

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);
}

糖逗