java 对称二叉树的判断

1. 题目描述

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

2. 解题思路

可以按照类似层次遍历，来判断是否是堆成二叉树：
首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同，以及左子树的右子树和右子树的左子树相同即可，然后采用递归一直判断下去。

3. 代码

public class isSymmetrical {

 public static void main(String[] args) {
 // 新建一棵二叉搜索树
 TreeNode root=new TreeNode(10);
 TreeNode n1=new TreeNode(5);
 TreeNode n2=new TreeNode(5);
 TreeNode n3=new TreeNode(4);
 TreeNode n4=new TreeNode(7);
 TreeNode n5=new TreeNode(7);
 TreeNode n6=new TreeNode(4);
 //TreeNode n7=new TreeNode(19);
 root.left=n1;
 root.right=n2;
 n1.left=n3;
 n1.right=n4;
 n2.left=n5;
 n2.right=n6;
 //n6.right=n7;

 System.out.println("后序遍历：");
 postOrderTraverse(root);

 boolean temp=symmetrical(root);
 System.out.println("\n"+"结果："+temp);
 }

 static boolean symmetrical(TreeNode pRoot)
  {
 if(pRoot == null){
      return true;
    }
    return comRoot(pRoot.left, pRoot.right);
  }

  static boolean comRoot(TreeNode left, TreeNode right) {
    if(left == null)
     return right==null;
    if(right == null)
     return false;
    if(left.val != right.val)
     return false;
    return comRoot(left.right, right.left) && comRoot(left.left, right.right);
  }

  // 后序遍历
  public static void postOrderTraverse(TreeNode node) {
    if (node == null)
      return;
    postOrderTraverse(node.left);
    postOrderTraverse(node.right);
    System.out.print(node.val + " ");
  }
}

运行：

后序遍历：
4 7 5 7 4 5 10
结果：true

到此这篇关于java 对称二叉树的判断的文章就介绍到这了,更多相关java 对称二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • PHP实现判断二叉树是否对称的方法

    本文实例讲述了PHP实现判断二叉树是否对称的方法.分享给大家供大家参考,具体如下: 问题 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 题解 递归判断二叉树两侧. 实现代码: <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ func

  • Python对称的二叉树多种思路实现方法

    对称二叉树的含义非常容易理解,左右子树关于根节点对称,具体来讲,对于一颗对称二叉树的每一颗子树,以穿过根节点的直线为对称轴,左边子树的左节点=右边子树的右节点,左边子树的右节点=左边子树的左节点.所以对称二叉树的定义是针对一棵树,而判断的操作是针对节点,这时可以采取由上到下的顺序,从根节点依次向下判断,只需要重复调用函数,不需要回溯. 题目:对称的二叉树题: 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的 解题思路一:先遍历右子节点再

  • java 对称二叉树的判断

    1. 题目描述 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 2. 解题思路 可以按照类似层次遍历,来判断是否是堆成二叉树: 首先根节点以及其左右子树,左子树的左子树和右子树的右子树相同,以及左子树的右子树和右子树的左子树相同即可,然后采用递归一直判断下去. 3. 代码 public class isSymmetrical { public static void main(String[] args) { // 新建一棵二叉搜索

  • java实现二叉树的创建及5种遍历方法(总结)

    用java实现的数组创建二叉树以及递归先序遍历,递归中序遍历,递归后序遍历,非递归前序遍历,非递归中序遍历,非递归后序遍历,深度优先遍历,广度优先遍历8种遍历方式: package myTest; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Stack; public class myClass { public static void main(

  • Java实现二叉树的建立、计算高度与递归输出操作示例

    本文实例讲述了Java实现二叉树的建立.计算高度与递归输出操作.分享给大家供大家参考,具体如下: 1. 建立 递归输出 计算高度 前中后三种非递归输出 public class Tree_Link { private int save = 0; private int now = 0; Scanner sc = new Scanner(System.in); /* * 构造函数 */ Tree_Link(){ } /* * 链表建立 */ public Tree Link_Build(Tree

  • Java求解二叉树的最近公共祖先实例代码

    Java求解二叉树的最近公共祖先实例代码

    一.题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先. 百度百科中最近公共祖先的定义为:"对于有根树 T 的两个结点 p.q,最近公共祖先表示为一个结点 x,满足 x 是 p.q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)." 例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4] 二.分析 本题需要找公共祖先,如果可以从下往上查找,就可以很方便的找到公共祖先 所以需要先访问叶子节点,然后在往上访问,对应着二叉树的

  • Java数据结构二叉树难点解析

    Java数据结构二叉树难点解析

    前言 本章,我们主要需要了解以下内容 什么是线索二叉树 怎么去把二叉树线索化 怎么通过线索二叉树查找某个数的后继结点 二叉树的查看--二叉树怎们遍历 什么是线索二叉树 首先我们来了解一下什么是线索二叉树? 定义:一个二叉树通过如下的方法"穿起来":所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继,所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱. 再看一下为什么要有线索二叉树? 顾名思义,线索二叉树,肯定是根据线索查找,查找速度肯定更快. 线索二叉树能线性地遍历二

  • Java实现二叉树的示例代码(递归&迭代)

    Java实现二叉树的示例代码(递归&迭代)

    目录 1.二叉树基本概念见上节:详解Java中二叉树的基础概念(递归&迭代) 2.本次展示链式存储 以此图为例,完整代码如下: //基础二叉树实现 //使用左右孩子表示法 import java.util.*; import java.util.Deque; public class myBinTree { private static class TreeNode{ char val; TreeNode left; TreeNode right; public TreeNode(char va

  • Java与JavaScript中判断两字符串是否相等的区别

    JavaScript是一种常用的脚本语言,这也决定了其相对于其他编程语言显得并不是很规范.在JavaScript中判断两字符串是否相等 直接用==,这与C++里的String类一样.而Java里的等号则是判断两字符串的引用是否一样,判断实体需要用equals()方法,或 者compareTo()方法,这里需要强调的是equals()方法的参数类型,其参数类型绝对不是String类,而是Object类,咱不止一次看 到国内一些教程写的是String类(o(╯□╰)o) 大家可以看看JDK的源码:

  • Java 对称加密几种算法分别实现

    Java 对称加密几种算法分别实现

    Java 对称加密使用DES / 3DES / AES 这三种算法分别实现 有两句话是这么说的: 1)算法和数据结构就是编程的一个重要部分,你若失掉了算法和数据结构,你就把一切都失掉了. 2)编程就是算法和数据结构,算法和数据结构是编程的灵魂. 注意,这可不是我说的,是无数程序员总结的,话说的很实在也很精辟,若想长久可持续发展,多研究算法还是很有必要的,今天我给大家说说加密算法中的对称加密算法,并且这里将教会大家对称加密算法的编程使用.包含DES.3DES和AES三种对称加密算法的编程使用,干货

  • Java基础教程_判断语句if else

    Java基础教程_判断语句if else

    与三元运算符相比: 好处:可以简化if else 代码 弊端 因为是一个运算符,所以运算玩必须要有一个结果 以上这篇Java基础教程_判断语句if else就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1. 分析 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列. 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树. 中序遍历:对任一子树,先遍历其左子树,然

随机推荐