剑指offer28.对称二叉树

剑指offer28.对称二叉树

题目描述

C++解法

#include<cstdio>
#include<stack>
#include<iostream>
using namespace std;

struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};
bool issymmetric(TreeNode* root1, TreeNode* root2)
{
    if (root1 == nullptr && root2 == nullptr)
        return true;

    if (root1 == nullptr && root2 != nullptr)
        return false;
    if (root1 != nullptr && root2 == nullptr)
        return false;
    if (root1->val != root2->val)
        return false;

    return issymmetric(root1->left, root2->right) && issymmetric(root1->right, root2->left);
}
//打印二叉树
static void printTree(TreeNode* node)
{
    if (node != nullptr)
    {
        
        printTree(node->left);
        cout << node->val << " ";
        printTree(node->right);
    }
}
void test( string name,TreeNode *tree1,TreeNode *tree2)
{
    bool res = issymmetric(tree1, tree2);
    if (res == false)
        cout << name << "不是对称二叉树" << endl;
    else
        cout << name << "是对称二叉树" << endl;
}
/* 完全二叉树：出来叶子节点，其他节点都有两个子节点
 *          8
 *       /     \
       6       10 
      / \      /  \
      5  7     9   11 
  */

void test1()
{
    cout << "测试完全二叉树" << endl;
    TreeNode* root = new TreeNode(8);
    root->left = new TreeNode(6);
    root->right= new TreeNode(10);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(7);
    root->right->left = new TreeNode(9);
    root->right->right = new TreeNode(11);
    printTree(root);
    test("text1", root, root);
}
void test2()
{
    cout << "测试完全二叉树" << endl;
    TreeNode* root = new TreeNode(8);
    root->left = new TreeNode(6);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(7);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(6);
    printTree(root);
    test("text2", root, root);
}
int main()
{
    test1();
    test2();
    return 0;
}