[剑指offer] 对称的二叉树

题目描述

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

解题思路

法一:递归。根节点的左右子树相同,左子树的左子树和右子树的右子树相同,左子树的右子树和右子树的左子树相同即可。 法二:非递归。非递归也是一样,采用栈或队列存取各级子树根节点。

参考代码

法一:递归。

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot == null)
            return true;
        return isSymmetrical(pRoot.left, pRoot.right);
    }
    boolean isSymmetrical(TreeNode left, TreeNode right){
        if(left == null && right == null)
            return true;
        if(left == null || right == null)
            return false;
        if(left.val == right.val){
            return isSymmetrical(left.left, right.right) && 
                isSymmetrical(left.right, right.left);
        }
        return false;
    }
}

法二:非递归。

import java.util.Stack;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot == null)
            return true;
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(pRoot.left);
        s.push(pRoot.right);
        while(!s.isEmpty()){
            TreeNode right = s.pop();
            TreeNode left = s.pop();
            if(right == null && left == null)
                continue;
            if(right == null || left == null)
                return false;
            if(right.val != left.val)
                return false;
            s.push(left.left);
            s.push(right.right);
            s.push(left.right);
            s.push(right.left);
        }
        return true;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

判断二叉树是否为平衡二叉树

解题思路: 根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过1,按照定义,它就是...

772
来自专栏尾尾部落

[剑指offer] 二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

882
来自专栏武培轩的专栏

剑指Offer-二叉树的镜像

package Tree; import java.util.ArrayDeque; import java.util.ArrayList; import j...

3384
来自专栏武培轩的专栏

剑指Offer-二叉树的深度

package Tree; import java.util.LinkedList; import java.util.Queue; /** * 二叉树...

3004
来自专栏武培轩的专栏

Leetcode#104. Maximum Depth of Binary Tree(二叉树的最大深度)

1492
来自专栏武培轩的专栏

剑指Offer-按之字形顺序打印二叉树

package Tree; import java.util.ArrayList; import java.util.LinkedList; import j...

2844
来自专栏desperate633

LeetCode Maximum Depth of Binary Tree题目分析代码

Given a binary tree, find its maximum depth.

681
来自专栏Python专栏

【数据结构与算法】一起搞定面试中的二叉树题目(二)

2243
来自专栏日常分享

Java 通过先序中序序列生成二叉树

  二叉树的前序以及后续序列,以空格间隔每个元素,重构二叉树,最后输出二叉树的三种遍历方式的序列以验证。

1901
来自专栏计算机视觉与深度学习基础

Leetcode 114 Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place. For example, Given...

2588

扫码关注云+社区

领取腾讯云代金券