• 关键字:二叉树
  • 难度:简单
  • 前置知识:二叉树
  • 题目大意:对于给出的一棵二叉树,判断其是否是对称的

题目描述

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3


解法

这是一道相对简单的题目,一种直接的思路,是将树按照中序遍历转化成数组,然后通过判断数组是否是回文的来判断这棵树是否是对称的。

而另一种方法,则是直接在对树的深度优先搜索中进行判断,即使用一个额外的指针root2

  • 当用于深度优先搜索的指针移动到左子树中时,root2就对应的移动到右子树当中
  • 当用于深度优先搜索的指针移动到右子树中时,root2就对应的移动到左子树当中

这样,在root2不能够对应移动,或者root1root2指向的节点的值不一样的时候,我们就可以知道这棵树是不对称的。

而当这样的过程正常的结束后,如果没有产生过错误,那么就说明这棵树是对称的~

参考代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return dfs(root, root);
    }
    bool dfs(TreeNode* root1, TreeNode* root2) {
        // 判断两个指针指向的值是否相同
        if (root1 -> val != root2 -> val) return false;
        // root2向root1的对称方向行动
        if (root1 -> left != NULL) {
            if (root2 -> right == NULL) return false;
            // 一旦发现存在不对称,立即退出
            if (!dfs(root1 -> left, root2 -> right)) return false;
        }
        if (root1 -> right != NULL) {
            if (root2 -> left == NULL) return false;
            if (!dfs(root1 -> right, root2 -> left)) return false;
        }
        return true;
    }
};

登录发表评论 注册

反馈意见