题解 | #对称的二叉树#

对称的二叉树

http://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb

思路

题目分析

题目给出一棵二叉树

我们需要判断这棵二叉树是否为左右镜像对称的，返回最终的判断结果

方法一：递归
- 我们构造一个递归函数，包含两个结点指针参数u,v，这两个结点指针参数本身就是在树中左右对称的
- 首先要判断两个节点指针本身是否互相对称
- 然后分别沿着左右子节点进行递归
  - u指针指向左子节点和v指针指向右子节点进行一次递归调用
  - u指针指向右子节点和v指针指向左子节点进行一次递归调用
- 返回判断的结果
方法二：迭代
- 我们借助队列结构
  - 首先根节点入队两次
  - 然后循环中每次提出两个节点判断对称性
  - 之后将两个节点的左右子节点按照相反的顺序插入队列中
- 对上述循环中每轮提取到的节点进行对称性判断，最终返回是否对称的结果

方法一：递归

alt


/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if(pRoot == NULL) return true;                    // 首先判断当前根节点是否为空
        return symmetrical(pRoot->left, pRoot->right);    // 调用递归函数向镜像的左右子树进行访问判断
    }
    
    bool symmetrical(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL) return true;           // 如果两指针都为NULL，则返回true
        if(p == NULL || q == NULL) return false;          // 如果其中一个非空，则返回false
        bool sameVal = q->val == p->val;                  // 如果俩结点都存在，则判断值是否相等，并递归判断镜像的子节点是否也相等
        return sameVal && symmetrical(p->left, q->right) && symmetrical(p->right, q->left);
    }

};

复杂度分析

时间复杂度： $O (N)$ ，遍历所有节点
空间复杂度： $O (l o g N)$ ，递归调用栈的空间消耗

方法二：迭代

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        return check(pRoot, pRoot);
    }
    
    bool check(TreeNode *u, TreeNode *v) {
        queue <TreeNode*> q;
        q.push(u); q.push(v);                   // 队列每两个位置存储一对即将需要判断是否对称的结点结点
        while (!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;             // 如果都为NULL则继续下一轮循环，说明可能为True
            if ((!u || !v) || (u->val != v->val)) return false;   //如果不对称则直接返回false
            // 对称地继续压入待判断的左右节点
            q.push(u->left);        
            q.push(v->right);
 
            q.push(u->right);
            q.push(v->left);
        }
        return true;
    }

};