找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ JAVA开发技术 ] 【守望者 j2se】java面试中的二叉树题目汇总

2014-10-11 16:52| 发布者: zhouy | 查看: 1276 | 收藏

摘要: 二叉树和链表一样,首先都应该想到递归。所以本文中尽量都用递归和非递归完成每一题1.二叉树的遍历,前序中序后序,递归和非递归2.二叉树的层序遍历3.二叉树的高度4.二叉树的节点个数5.求二叉树的镜像6.判断两颗二叉 ...

二叉树和链表一样,首先都应该想到递归。所以本文中尽量都用递归和非递归完成每一题


1.二叉树的遍历,前序中序后序,递归和非递归

2.二叉树的层序遍历

3.二叉树的高度

4.二叉树的节点个数

5.求二叉树的镜像

6.判断两颗二叉树是否互为镜像

7.判断一棵树是否本身就是镜像树

8.判断两颗二叉树是不是相同的树

9.判断树1是不是树2的子结构

10.判断二叉树是否是平衡二叉树

11.二叉树第k层的节点个数

12.二叉树叶子节点的个数

13.由前序遍历和中序遍历重构二叉树

14.由中序遍历和后序遍历重构二叉树

15.二叉树中两节点的最大距离

16.二叉树中和为某一值的路径

17.求二叉树中两个节点的最低公共祖先节点


package com.sheepmu;

import java.util.LinkedList;
import java.util.Stack;

class TreeNode
{
  String value;
  TreeNode left;
  TreeNode right;
  public TreeNode(String value ) 
  {
    this.value = value;
  }

}

public class BinaryTree 
{
  //2.二叉树的层序遍历
  //思路:利用队列实现二叉树的层序遍历。
  public  void cx(TreeNode root)
  {
    if(root==null)
      return;
    LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
    queue.addLast(root);
    while(!queue.isEmpty())
    {
      TreeNode cur=queue.removeFirst();
      System.out.print(cur.value+" ");
      if(cur.left!=null) 
        queue.addLast(cur.left);                        
      if(cur.right!=null)         
        queue.addLast(cur.right);
                
    }
  }

  //3.二叉树的高度  --递归--
  public  int getHighRec(TreeNode root)
  {
    if(root==null)
      return 0;
    return Math.max(getHighRec(root.left), getHighRec(root.right))+1;
  }

  //4二叉树的高度  --非 递归--
  //思路:层序遍历,对当前层和下一层的节点数计数。
  public  int getHigh(TreeNode root)
  {
    if(root==null)
      return 0;
    LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
    queue.addLast(root);
    int high=0;
    int curLevelNodes=1,nextLevelNodes=0;
    while(!queue.isEmpty())
    {
      TreeNode cur=queue.removeFirst();
      curLevelNodes--;
      if(cur.left!=null)
      {
        queue.addLast(cur.left);
        nextLevelNodes++;
      }
      if(cur.right!=null)
      {
        queue.addLast(cur.right);
        nextLevelNodes++;
      }
      if(curLevelNodes==0)
      {
        high++;
        curLevelNodes=nextLevelNodes;
        nextLevelNodes=0;
      }        
    }
    return high;                 
  }

  //4.二叉树的节点个数   --递归--
  public  int getNodesNumRec(TreeNode root)
  {
    if(root==null)
      return 0;
    return getNodesNumRec(root.left)+getNodesNumRec( root.right)+1;
  }
  //5二叉树的节点个数   --递归--
  //思路:层序遍历记录个数
  public  int getNodesNum(TreeNode root)
  {
    if(root==null)
      return 0;
    LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
    queue.addLast(root);
    int num=1;
    while(!queue.isEmpty())
    {
      TreeNode cur=queue.removeFirst();
      if(cur.left!=null)
      {
        queue.addLast(cur.left);
        num++;
      }
      if(cur.right!=null)
      {
        queue.addLast(cur.right);
        num++;
      }
    }
    return num;
  }

  //6.求二叉树的镜像(直接把原树变为其镜像树,即破坏原树)   --递归--
  //思路:把原树的左子树置为其右子树的镜像;把原树的右子树置为其左子树的镜像
  public  TreeNode getJXRec(TreeNode root)
  {
    if(root==null)
      return null;
    TreeNode tleft=getJXRec(root.right);
    TreeNode tright=getJXRec(root.left);
    root.left=tleft;
    root.right=tright;
    return root;
  }

  //7.求二叉树的镜像(直接把原树变为其镜像树,即破坏原树)   --非递归--
  //思路: 利用Stsck,让节点的子节点互相交换
  public  TreeNode getJX(TreeNode root)
  {
    if(root==null)
      return null;
     Stack<TreeNode> stack=new Stack<TreeNode>();
     stack.push(root);
     while(!stack.isEmpty())
     {
       TreeNode cur=stack.pop();
       TreeNode temp=cur.right;
       cur.right=cur.left;
       cur.left=temp;
       if(cur.right!=null)
         stack.push(cur.right);
       if(cur.left!=null)
         stack.push(cur.left);
     }
    return root; 
  }

  //8.求二叉树的镜像(生成一颗新树,即不改变原树结构) --递归--
  public TreeNode newJXRec(TreeNode root)
  {
    if(root==null)
      return null;
    TreeNode newTree=new TreeNode (root.value);
    newTree.left=newJXRec(root.right);
    newTree.right=newJXRec(root.left);
    return newTree;
  }


  //8.求二叉树的镜像(生成一颗新树,即不改变原树结构) --非 递归--

  /* 
                                A  
                               /   \  
                             B      C  
                            / \        \  
                          D    E        F  
  */  
  public static void main(String[] args)
  {
    TreeNode n1=new TreeNode("A");
    TreeNode n2=new TreeNode("B");
    TreeNode n3=new TreeNode("C");
    TreeNode n4=new TreeNode("D");
    TreeNode n5=new TreeNode("E");
    TreeNode n6=new TreeNode("F");
    n1.left=n2;
    n1.right=n3;
    n2.left=n4;
    n2.right=n5;
    n3.right=n6;
    TreeNode root=n1;
    BinaryTree bt=new BinaryTree();
    System.out.print("层序遍历---->" );
    bt.cx(root);
    System.out.print("\n");
    System.out.println("递归高度---->"+bt.getHighRec(root));
    System.out.println("非递归高度---->"+bt.getHighRec(root));
    System.out.println("递归节点个数---->"+bt.getNodesNumRec(root));
    System.out.println("非递归节点个数---->"+bt.getNodesNum(root));

//                 bt.getJXRec(root);
//                 bt.cx(root);
//                 System.out.print("\n");
    System.out.print("把树变为本身的镜像树后层序遍历---->" );
     bt.getJX(root);
     bt.cx(root);

  }
}


本文由守望者watchmen收集整理,部分内容源于网络(www.tuicool.com)。本文仅代表作者个人观点,不代表守望者的本意。如有违法侵权内容,请提交到守望者管理员处,立即处理。

推荐阅读

【守望者  j2se】ConcurrentHashMap原理分析
【守望者 j2se】ConcurrentHashMap原
集合是编程中最常用的数据结构。而谈到并发,几乎总是离不开集合这类高级数据
【守望者  j2se】双向链表模拟
【守望者 j2se】双向链表模拟
我们熟悉了java单向链表的模拟,现在我就必须开始双向链表的模拟的.1.基础结构
【守望者 高并发】现有高并发WEB服务器 lighttpd Apache Nginx比较
【守望者 高并发】现有高并发WEB服务器
lighttpd网络服务器基于的Lighttpd的网络服务器具有这样的特点:占用内存资源
【守望者 高并发】C10K/C500K与I/O框架
【守望者 高并发】C10K/C500K与I/O框架
C10K、C/500K问题C10K 的意思是10000并发请求,C500K意思是500 000并发请求,
【守望者  j2se】虚拟机各部分内存溢出情况
【守望者 j2se】虚拟机各部分内存溢出
通过简单的小例子程序,演示java虚拟机各部分内存溢出情况:(1).java堆溢出:
【守望者  JMM】理解volatile内存语义
【守望者 JMM】理解volatile内存语义
理解volatile变量对写多线程程序还是很有帮助的,这样就会避免一上来就是syn这
【守望者 高并发】使用CAS实现高效并发处理
【守望者 高并发】使用CAS实现高效并发
守望者:在并发处理应用中,一般使用锁的方式来解决竞争问题,但锁的效率比较
【守望者  j2se】吃透 java I/O 工作机制-1
【守望者 j2se】吃透 java I/O 工作机
I/O 问题可以说是当今互联网 Web 应用中所面临的主要问题之一,因为当前在这
【守望者 大数据】Mahout学习路线图
【守望者 大数据】Mahout学习路线图
Hadoop家族产品,常用的项目包括Hadoop, Hive, Pig, HBase, Sqoop, Mahout, Z
【守望者 j2se】ConcurrentMap之putIfAbsent(key,value)用法讨论
【守望者 j2se】ConcurrentMap之putIfA
先看一段代码:public class Locale { private final static MapString, Lo
【守望者  javascript】判断IE浏览器世界上最短的代码
【守望者 javascript】判断IE浏览器世
最短的IE判定var ie=!-分析以前最短的IE判定借助于IE不支持垂直制表符的特性
【守望者 大数据】机器学习已成为大数据的基石
【守望者 大数据】机器学习已成为大数
机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、
【守望者  j2se】多线程与并发知识点总结
【守望者 j2se】多线程与并发知识点总
对于多线程和并发编程这个比较大的技术模块,我们会整理一些帖子方便知识点的
【守望者  j2se】二叉树模拟
【守望者 j2se】二叉树模拟
接着我们就要写一个比较复杂的数据结构的,但是这个数据结构是很重要的,假如
【守望者 SRS  】SRS 源代码分析笔记(0.9.194)-分析服务器对端口的监听 ...
【守望者 SRS 】SRS 源代码分析笔记(
第一部分 分析服务器对端口的监听 端口监听与初始化(一)全局变量_srs_confi

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  W3Cfuns前端网  中国企业家  环球企业家  投资界  传媒梦工场  MSN中文网  Android开发者社区  cnbeta  投资中国网  又拍云存储  美通说传播  IT茶馆  网商在线  商业评论网  TechOrange  IT时代周刊  3W创新传媒  开源中国社区  二维工坊  Iconfans  推酷  智能电视网  FreeBuf黑客与极客  财经网  DoNews  凤凰财经  新财富  eoe移动开发者社区  i黑马  网易科技  新浪科技  搜狐IT  创业家  创业邦  腾讯财经  福布斯中文网  天下网商  TechWeb  雷锋网  新浪创业  和讯科技  品途O2O  极客公园  艾瑞网  抽屉新热榜  卖家网  人民网通信频道  拉勾网  创新派  简单云主机  

手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据 ( 蜀ICP备14029946号

成都守望者科技有限公司 © 2013-2016 All Rights Reserved