剑指offer | 28. 对称的二叉树

本是古典何须时尚 2022-12-27 09:15 86阅读 0赞

**题目内容：**

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

例如，二叉树 [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

--------------------

**方法一：递归**

*  首先要记得，这里的对称是指镜像的对称，比较的是左右子树，而不是左右孩子，也就是你要比较左子树的左孩子和右子树的右孩子是否相等。
 *  还有时刻记得要排除结点为空的各种情况。
 *  一个清晰的递归解题思路是：
    
     *  确定递归的参数：根节点的左右两个子树
     *  确定终止条件：
        
         *  都为空指针 返回true
         *  只有一个位空指针 返回false
         *  两个当前结点值不相等 返回false
     *  递归过程：
        
         *  判断A的右子树与B的左子树是否对称
         *  判断A的左子树与B的右子树是否对称

class Solution { 
    public:
        bool isSymmetric(TreeNode* root) { 
            bool res = true;
            if (root!=NULL)
            { 
                res = helper(root->left,root->right);
            }
            return res;
        }
    
        bool helper(TreeNode*A, TreeNode* B)
        { 
            // 先写递归终止条件
            if (A==NULL && B==NULL)
                return true;
            // 如果其中之一为空，也不是对称的
            if (A==NULL || B==NULL)
                return false;
            // 走到这里二者一定不为空
            if (A->val != B->val)
                return false;
            // 前序遍历
            return helper(A->left,B->right) && helper(A->right,B->left);
        }
    };

*  时间复杂度：O（n）遍历整个树一次，n为树的结点数目。
 *  空间复杂度：O（n）递归调用的次数受树的高度限制。在最糟糕的情况下树是线性的，其高度为O（n）。

**方法二：迭代法**

*  利用队列进行迭代。按照前序遍历的话：根左右，即队列中每两个连续的结点是相等的，而且题目的子树互为镜像。
 *  类似BFS，但区别在于：每次提取两个结点并比较它们的值。然后将两个结点的左右子树结点按相反的顺序插入到队列中。当队列为控，或者检测到树不对称（即两个连续的点不相等，算法结束）。

class Solution { 
    public:
        bool isSymmetric(TreeNode* root) { 
            if (root ==NULL)
                return true;
            //用队列保存节点
            queue<TreeNode*> q;
            //将根节点的左右孩子放到队列中
            q.push(root->left);
            q.push(root->right);
            while(!q.empty())
            { 
                //从队列中取出两个节点，再比较这两个节点
                TreeNode* A = q.front();
                q.pop();
                TreeNode* B = q.front();
                q.pop();
                //如果两个节点都为空就继续循环，两者有一个为空就返回false
                if (A==NULL && B==NULL)
                    continue;
                if (A==NULL || B==NULL)
                    return false;
                if (A->val != B->val)
                    return false;
                //将左子树的左孩子， 右子树的右孩子放入队列
                q.push(A->left);
                q.push(B->right);
                //将左子树的右孩子，右子树的左孩子放入队列
                q.push(A->right);
                q.push(B->left);
            }
            return true;
        }
    };

*  时间复杂度O（n），遍历整个树一遍，n为结点个数
 *  空间复杂度O（n），搜索队列需要额外空间。最糟糕的情况下要向队列中插入O（n）个结点。

参考：

*  [对称二叉树:【递归法】【迭代法】详解！][Link 1]
 *  [C++与Python两种解法实现：递归与迭代][C_Python]

[Link 1]: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/solution/dui-cheng-er-cha-shu-di-gui-fa-die-dai-fa-xiang-ji/
[C_Python]: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/solution/cyu-pythonliang-chong-jie-fa-shi-xian-di-gui-yu-di/