对称二叉树

compare的用法：

在图中的代码里， compare  函数是用于判断二叉树两棵子树是否对称的自定义函数 ，其用法要点如下：
函数定义
cpp
bool compare(TreeNode* left, TreeNode* right) {
    // 函数体内容
}
- 返回值类型： bool  类型，用于返回两棵子树是否对称的结果， true  表示对称， false  表示不对称。
- 参数：接收两个参数  TreeNode* left  和  TreeNode* right  ，分别是指向两棵待比较子树的根节点的指针。

函数内部逻辑

1. 空节点处理：

通过一系列  if - else if  语句，先判断各种空节点情况。比如  if (left == NULL && right!= NULL)  ，若左子树为空而右子树不为空，直接返回  false  ，因为这种情况两棵子树不对称；类似地，对其他空节点组合情况进行判断并返回相应结果。当  left == NULL && right == NULL  时，说明这部分子树对称，返回  true  。

2.. 节点值比较：

排除空节点情况后，用  else if (left->val!= right->val)  判断左右子树对应节点的值是否相等，若不相等，返回  false  ，表示子树不对称。

3. 递归调用：

在左右子树节点都不为空且节点值相等时，通过递归调用  compare  函数来比较更深层次的子树。例如  compare(left->left, right->right)  ，比较左子树的左子树和右子树的右子树； compare(left->right, right->left)  ，比较左子树的右子树和右子树的左子树 。最后将这两个递归比较结果通过逻辑与（ &&  ）运算合并，得到最终两棵子树是否对称的结果并返回。

函数调用

在  isSymmetric  函数中，通过  compare(root->left, root->right)  调用  compare  函数，传入根节点的左右子树，以此开始判断整棵二叉树是否对称的流程 。

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

方法一递归法思路：

一、确定递归函数的参数和返回值。

        参数是左子树节点和右子树节点。返回值自然是bool类型。

二、确定终止条件。

1.有空节点时。

 （1）左节点为空，右节点不为空。 return false。

 （2）左节点不为空，右节点为空。 return false。

 （3）左右节点都为空。 return true。

2.没有空节点

   看左右孩子是否对称。

三、确定单层递归的逻辑。

此时进入单层递归的逻辑，单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况。

1.比较二叉数外侧是否对称：传入的是左节点的左孩子右节点的右孩子。

2.比较内侧是否对称：传入的是左节点的右孩子，右节点的左孩子。

3.如果左右都对称就返回true，有一侧不对称就返回false。

class Solution {
public:bool compare(TreeNode*left,TreeNode*right){if(left==NULL&&right!=NULL) return false;else if(left!=NULL&&right==NULL) return false;else if(left==NULL&&right==NULL) return true;else if(left->val!=right->val) return false;bool outside=compare(left->left,right->right);bool inside=compare(left->right,right->left);bool isside=inside&&outside;return isside;}bool isSymmetric(TreeNode* root) {if(root==NULL) return true;return compare(root->left,root->right);}
};

方法二迭代法思路：

一、使用队列来比较两个树是否反转

class Solution {
public:bool isSymmetric(TreeNode* root) {if(root==NULL) return true;queue<TreeNode*>que;que.push(root->left);que.push(root->right);while(!que.empty()){TreeNode*leftnode=que.front(); que.pop();TreeNode*rightnode=que.front(); que.pop();if(!leftnode&&!rightnode){continue;}if((!leftnode||!rightnode||(leftnode->val!=rightnode->val))){return false;}que.push(leftnode->left);que.push(rightnode->right);que.push(leftnode->right);que.push(rightnode->left);}return true;}
};

二、使用栈比较两个树是否反转

把两个子树要比较的元素放进一个容器，然后成对的取出来进行比较。

class Solution {
public:bool isSymmetric(TreeNode* root) {if(root==NULL) return true;stack<TreeNode*>st;st.push(root->left);st.push(root->right);while(!st.empty()){TreeNode*leftnode=st.top(); st.pop();TreeNode*rightnode=st.top(); st.pop();if(!leftnode&&!rightnode){continue;}if((!leftnode||!rightnode||(leftnode->val!=rightnode->val))){return false;}st.push(leftnode->left);st.push(rightnode->right);st.push(leftnode->right);st.push(rightnode->left);}return true;}
};