【数据结构和算法】递归和非递归两种方式解决

判断二叉树是否对称

http://www.nowcoder.com/practice/1b0b7f371eae4204bc4a7570c84c2de1

递归解决

判断二叉树是否是对称,需要从子节点开始比较,两个子节点的值必须相同,并且左子节点的右子节点(如果有)必须等于右子节点的左子节点,左子节点的左子节点必须等于右子节点的右子节点。就像下面图中那样

图片说明

 public boolean isSymmetric (TreeNode root) {
    if (root == null)
        return true;
    //从两个子节点开始判断
    return isSymmetricHelper(root.left, root.right);
}

public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
    //如果左右子节点都为空,说明当前节点是叶子节点,返回true
    if (left == null && right == null)
        return true;
    //如果当前节点只有一个子节点或者有两个子节点,但两个子节点的值不相同,直接返回false
    if (left == null || right == null || left.val != right.val)
        return false;
    //然后左子节点的左子节点和右子节点的右子节点比较,左子节点的右子节点和右子节点的左子节点比较
    return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
}

非递归解决

非递归解决和上面原理一样,直接看下代码,代码中有详细注释

 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;
}

总结

树的镜像判断,首先需要要找准判断的两个节点,然后再比较,比较完之后如果值相同,还有继续比较两个子节点。

如果觉得有用就给个赞吧,还可以关注我的《牛客博客》查看更多的详细题解

数据结构和算法 文章被收录于专栏

专注于算法题的讲解,包含常见数据结构,排序,查找,动态规划,回溯算法,贪心算法,双指针,BFS和DFS等等。

全部评论

相关推荐

看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-27 18:00
点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
水墨不写bug:疑似没有上过大学
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务