|
二叉树和链表一样，首先都应该想到递归。所以本文中尽量都用递归和非递归完成每一题 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)。本文仅代表作者个人观点，不代表守望者的本意。如有违法侵权内容，请提交到守望者管理员处，立即处理。 |
行业聚焦 面试交流 职位推荐 开发视频 技术交流 腾讯微博 新浪微博
友情链接：课课家教育 阿里云 鲜果 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
收藏