算法15.对称的二叉树 |

二叉树递归辅助栈

算法

发布日期: 2020-10-27

更新日期: 2020-10-27

文章字数: 635

阅读次数:

题目描述

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

示例 1：

二叉树 [1,2,2,3,4,4,3] 是对称的。
    1
   / \
  2   2
 / \ / \
3  4 4  3

示例 2：

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    1
   / \
  2   2
   \   \
   3    3

解题思路

方法一：递归分析

时间复杂度：$O(N)$

空间复杂度：$O(N)$

代码如下

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

解法分析

每一次递归传进左子树指针和右子树指针。终止条件为下面几种情况：

左右子树都为空，返回$True$
左右子树值不等或者只有一边为空，返回$False$
返回递归函数，函数参数是左子树的左子树和右子树的右子树比较；与左子树的右子树和右子树的左子树比较。

方法二：辅助栈方法

时间复杂度：$O(N)$

空间复杂度：$O(N)$

代码如下

//摘自LeetCode中sdwwld大佬
public boolean isSymmetric(TreeNode root) {
    //队列
    Queue<TreeNode> queue = new LinkedList<>();
    if (root == null)
        return true;
    //左子节点和右子节点同时入队
    queue.add(root.left);
    queue.add(root.right);
    //如果队列不为空就继续循环
    while (!queue.isEmpty()) {
        //每两个出队
        TreeNode left = queue.poll(), right = queue.poll();
        //如果都为空继续循环
        if (left == null && right == null)
            continue;
        //如果一个为空一个不为空，说明不是对称的，直接返回false
        if (left == null ^ right == null)
            return false;
        //如果这两个值不相同，也不是对称的，直接返回false
        if (left.val != right.val)
            return false;
        //这里要记住入队的顺序，他会每两个两个的出队。
        //左子节点的左子节点和右子节点的右子节点同时
        //入队，因为他俩会同时比较。
        //左子节点的右子节点和右子节点的左子节点同时入队，
        //因为他俩会同时比较
        queue.add(left.left);
        queue.add(right.right);
        queue.add(left.right);
        queue.add(right.left);
    }
    return true;
}