public TreeNode buildTree(int[] inorder, int[] preorder) {//由前序序列和中序序列重建二叉树
if(inorder.length<1||preorder.length<1||inorder.length!=preorder.length){
return null;
}
return constructTree(inorder, 0, inorder.length-1, preorder, 0, preorder.length-1);
}
public TreeNode constructTree(int[] inorder,int inBegin,int inEnd,int[] preorder,int preBegin,int preEnd){
int val = preorder[preBegin];
TreeNode rootNode = new TreeNode(val);
rootNode.left = rootNode.right = null;
if(inBegin == inEnd){
if(preBegin == preEnd&&inorder[inBegin] == preorder[preBegin]){
return rootNode;
}
}
//在中序遍历中找到根节点
int rootIndex = inBegin;
while(inorder[rootIndex]!=val&&rootIndex<=inEnd){
rootIndex++;
}
//找到rootIndex，分左右子树。分别找到中序、前序的左子树的结尾，右子树的开始
//左子树长度
int leftLength = rootIndex-inBegin;
//右子树长度
int rightLength = inEnd-rootIndex;
//中序
int inLeftEnd = rootIndex-1;
int inRightBegin = rootIndex+1;
//前序
int preLeftEnd = preBegin+leftLength;
int preRightBegin = preLeftEnd+1;
//构建左、右子树
if(leftLength>0){
rootNode.left = constructTree(inorder, inBegin, inLeftEnd, preorder, preBegin+1, preLeftEnd);
}
if(rightLength>0){
rootNode.right = constructTree(inorder, inRightBegin, inEnd, preorder, preRightBegin, preEnd);
}
return rootNode;
}
//根据中序遍历序列和后序遍历序列构造二叉树。
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length!=postorder.length||inorder.length==0||postorder.length==0){
return null;
}
return constructTreeNode(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
}
public TreeNode constructTreeNode(int[] inorder,int inBegin,int inEnd,
int[] postorder,int postBegin,int postEnd){
int val = postorder[postEnd];
TreeNode rootNode = new TreeNode(val);
rootNode.left = rootNode.right = null;
//中序遍历中有一个节点
if(inBegin==inEnd){
//再判断后序遍历中也只有一个节点，且中序和后序中两个节点相等，则返回
if(postBegin==postEnd&&inorder[inEnd]==postorder[postEnd]){
return rootNode;
}//其他的情况就报错。说明输入序列非法
}
int rootIndex = inBegin;
//先在中序遍历中找到根节点，分成左右子树
while(inorder[rootIndex]!=val&&rootIndex<=inEnd){
rootIndex++;
}
//中序分为左右两子树
int leftLength = rootIndex-inBegin;
int inLeftEnd = rootIndex-1;
int inRightBegin = rootIndex+1;
int postLeftEnd = postBegin+leftLength-1;
int postRightBegin = postLeftEnd+1;
int rightLength = inEnd-rootIndex;
if(leftLength>0){
rootNode.left = constructTreeNode(inorder,inBegin,inLeftEnd,postorder,postBegin,postLeftEnd);
}
if(rightLength>0){
rootNode.right = constructTreeNode(inorder,inRightBegin,inEnd,postorder,postRightBegin,postEnd-1);
}
return rootNode;
}
3.求二叉树的所有路径
思路：（1）递归调用 public List binaryTreePaths(TreeNode root) {
String path = "";
List list = new ArrayList();
if(root==null){
return list;
}
getPath(root,list,path);
return list;
}
public void getPath(TreeNode node,List list,String path){
path +=node.val+"->";
if(node.left==null&&node.right==null){
list.add(path.substring(0,path.length()-2));
}
if(node.left!=null){
getPath(node.left, list, path);
}
if(node.right!=null){
getPath(node.right, list, path);
}
}
（2）栈+递归：见下一题《判断二叉树中是否存在一条路径使得节点之和为给定的值》
（3）定义一个node新结构，每个节点都存放（节点，根节点到其路径）/*用栈来实现，新建一个结构，每个节点存放从根节点开始的路径。*/
private static class nodePath{
public TreeNode node;
public String path;
public nodePath(TreeNode node,String path){
this.node = node;
this.path = path;
}
}
public List binaryTreePaths(TreeNode root) {
List list = new ArrayList();
Stack path = new Stack();
if(root==null){
return list;
}
path.push(new nodePath(root, root.val+"->"));
while(!path.isEmpty()){
nodePath nodePath = path.peek();
TreeNode curNode = path.pop().node;
if(curNode.left==null&&curNode.right==null){
String result = nodePath.path;
list.add(result.substring(0,result.length()-2));
}
if(curNode.left!=null){
path.push(new nodePath(curNode.left, nodePath.path+curNode.left.val+"->"));
}
if(curNode.right!=null){
path.push(new nodePath(curNode.right, nodePath.path+curNode.right.val+"->"));
}
}
return list;
}
4.判断二叉树中是否存在一条路径使得节点之和为给定的值。
思路：递归实现，找路径的时候，记录当前Sum和目标和，递归结束条件：当是叶子节点且当前sum=目标值。将path放入list中public boolean hasPathSum(TreeNode root, int sum) {
if(root==null){
return false;
}
if(root.left==null&&root.right==null){
return root.val==sum;
}
List list = new ArrayList();
Stack stack = new Stack();
int curSum = 0;
getAllPath(root, stack, curSum,sum,list);
boolean result = false;
if(list.size()>0){
return true;
}
return result;
}
public void getAllPath(TreeNode rootNode,Stack stack,int curSum, int expectedSum,List list){
stack.push(rootNode);
curSum+=rootNode.val;
boolean isLeaf = rootNode.left==null&&rootNode.right==null;
if(isLeaf && curSum==expectedSum){
//把栈中的元素拿出来，组成数字
Iterator iterator = stack.iterator();
String path = "";
while(iterator.hasNext()){
path+=iterator.next().val+"->";
}
System.out.println(path);
list.add(path.substring(0,path.length()-2));
}
if(rootNode.left!=null){
getAllPath(rootNode.left, stack, curSum,expectedSum,list);
}
if(rootNode.right!=null){
getAllPath(rootNode.right, stack,curSum,expectedSum,list);
}
//返回父节点之前要先弹出
stack.pop();
}5、求二叉树的最大深度、最小深度
最大深度：分别求左右子树的深度，其最大值即为二叉树的最大深度。最小深度：容易出错，必须是根到叶子节点的高度的最小值。所以归结为求二叉树所有路径中的最小值即为最小深度。//求最大深度
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return maxDepthRecursion(root, 1);
}
public int maxDepthRecursion(TreeNode node,int depth){
int leftDepth = depth;
int rightDepth = depth;
if(node.left!=null){
leftDepth = maxDepthRecursion(node.left, leftDepth+1);
}
if(node.right!=null){
rightDepth = maxDepthRecursion(node.right, rightDepth+1);
}
return Math.max(leftDepth, rightDepth);
}
//树的最小深度
public int minDepth(TreeNode root) {
if(root==null){
return 0;
}
List list = new ArrayList();
getAllPath(root, list, "");
//将list中path按逗号查分
String pathStr = list.get(0).trim();
String[] pathArry = pathStr.split(",");
int minDepth = pathArry.length;
for(String path:list){
pathArry = path.split(",");
if(pathArry.length minDepth = pathArry.length;
}
}
return minDepth;
}
public void getAllPath(TreeNode node,List list,String path){
path+=node.val+",";
if(node.left==null&&node.right==null){
list.add(path);
}
if(node.left!=null){
getAllPath(node.left, list, path);
}
if(node.right!=null){
getAllPath(node.right, list, path);
}
}
6、求二叉树第k层的节点个数
思路1：层次遍历（队列)见题1解法，可求得k层的节点个数思路2: （1）当k<1时，返回0（2）当k=1时返回1（3）当k>1时，递归调用，返回（左子树的k-1层的节点数+右子树的k-1层节点数）public int getKLevelNum(TreeNode root,int k){
if(root==null||k<1){
return 0;
}
if(k==1){
return 1;
}
int leftNum = getKLevelNum(root.getLeftChild(), k-1);
int rightNum = getKLevelNum(root.getRightChild(), k-1);
return leftNum+rightNum;
}7、求二叉树中叶子节点的个数
思路 （1）当根节点为null时返回0（2）当遇到叶子节点返回1，（3）递归返回左右子树的叶子节点，相加public int getLeafCount(Node root){
if(root == null){
return 0;
}
if(root.getLeftChild()==null&&root.getRightChild()==null){
return 1;
}
int leftLeafNum = getLeafCount(root.getLeftChild());
int rightLeafNum = getLeafCount(root.getRightChild());
return leftLeafNum+rightLeafNum;
}8、求二叉树的镜像：交换二叉树的左右孩子
思路：（1）根节点为null,return（2）交换节点的左右孩子 swap（3）左、右子树分别递归实现public TreeNode invertTree(TreeNode root) {
if(root==null){
return null;
}
if(root.left==null&&root.right==null){
return root;
}
//交换左右子节点
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left!=null){
invertTree(root.left);
}
if(root.right!=null){
invertTree(root.right);
}
return root;
} 9、判断两棵二叉树是否相同（结构和值都相等）
思路：相同包括：位置相同、值相同。（1）根节点为空，return false.（2）只有根节点（左右节点均为null），return true,（3）左节点、右节点有一个null,return false;（4）左右节点不为空，值是否相同（5）分别递归判断左、右子树public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null){
return true;
}else if(p==null||q==null){
return false;
}
if(p.val!=q.val){
return false;
}
boolean left = true;
boolean right = true;
return traversalTree(p, q, left, right);
}
public boolean traversalTree(TreeNode p, TreeNode q,boolean left,boolean right){
if(p==null&&q==null){
return true;
}
else if(p==null||q==null){
return false;
}
if(p.val!=q.val){
return false;
}
left = traversalTree(p.left, q.left, left, right);
right = traversalTree(p.right, q.right, left, right);
return left&&right;
} 10、判断二叉树是否为完全二叉树
完全二叉树的特点：若设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边。
思路：层次遍历（从上到下，从左到右）当遇到一个节点的左子树为空，其右子树必须为空，且后面遍历的节点的左右子树都必须为空。
public boolean isCompleteBinaryTree(TreeNode rootNode){
if(rootNode==null){
return false;
}
//层次遍历二叉树
Queue queue = new Queue(1024);
queue.push(rootNode);
boolean haveNoChild = false;
while(!queue.isEmpty()){
TreeNode curNode = queue.pop();
if(haveNoChild){
//当出现空子树节点的时候，后面出现的必须为叶子节点
if(curNode.getLeftChild()!=null||curNode.getRightChild()!=null){
return false;
}
}
if(curNode.getLeftChild()!=null&&curNode.getRightChild()!=null){
queue.push(curNode.getLeftChild());
queue.push(curNode.getRightChild());
}else if(curNode.getLeftChild()!=null&&curNode.getRightChild()==null){
//只有左节点时，后面的节点都应为叶子节点
haveNoChild = true;
queue.push(curNode.getLeftChild());
}else if(curNode.getLeftChild()==null&&curNode.getRightChild()!=null){
return false;
}else {
//此节点为叶子节点
haveNoChild = true;
}
}
return true;
}11、判断二叉树是否为平衡二叉树
思路：（1）如果二叉树为空，返回真
（2）如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假public boolean isAVLBTree(Node rootNode){
if(rootNode==null){
return false;
}
return isAVL(rootNode, 1);
}
public boolean isAVL(Node rootNode,int depth){
int leftDepth = depth;
int rightDepth = depth;
if(rootNode==null){
return true;
}
booleanisAVL_left = isAVL(rootNode.getLeftChild(), leftDepth+1);//求深度
boolean isAVL_right = isAVL(rootNode.getRightChild(), rightDepth+1);
if(isAVL_left&&isAVL_right&&Math.abs(leftDepth - rightDepth)<=1){
return true;
}
return false;
}12、判断二叉树是否关于根节点对称（类似镜子） 1
/ \
2 2
/ \ / \
3 4 4 3
思路：递归解法（1）如果二叉树为空，返回空（2）如果二叉树不为空，则递归判断节点的左右节点a.同时为空，则return trueb某一个节点为空则 return falsec.都不为空但值不等，则 return falsepublic boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
//只有根节点
if(root.left==null&&root.right==null){
return true;
}
return isSymmetricChildTree(root.left,root.right);
}
public boolean isSymmetricChildTree(TreeNode left,TreeNode right){
if(left==null&&right==null){
return true;
}
if((left!=null&&right==null)||(left==null&&right!=null)){
return false;
}
if(left.val!=right.val){
return false;
}
return isSymmetricChildTree(left.left, right.right)&&isSymmetricChildTree(left.right, right.left);
}13、输入两棵二叉树A和B，判断B是否为A的子树思路：（1）如果两棵树都为空，则return true （2）如果两棵树都不为空，则在A中找B节点（递归查看左右子树） （3）在A中找到B根节点以后判断其两棵树的左右子树是否相同。//输入两棵二叉树A和B，判断B是否为A的子树
//遍历首先看A中是否有B的根节点。有的话查看该节点下的左右子节点。如果没有继续查找直到叶子节点。
//用递归遍历
//二叉树遍历 访问每个地址时，都要考察是否为null,为null时如何处理
public boolean HasSubTree(BinaryTreeNode aRoot,BinaryTreeNode bRoot){
boolean isHas = false;
if(aRoot!=null&&bRoot!=null){
if(aRoot.getKey() == bRoot.getKey()){
//开始比对左右子节点
isHas = isEqualChildTree(aRoot,bRoot);
}
if(!isHas){
isHas = HasSubTree(aRoot.getLeftNode(), bRoot);
}
if(!isHas){
isHas = HasSubTree(aRoot.getRightNode(), bRoot);
}
}
return isHas;
}
public boolean isEqualChildTree(BinaryTreeNode aRoot,BinaryTreeNode bRoot){
if(bRoot == null){
return true;
}
if(aRoot == null){
return false;
}
if(aRoot.getKey()!=bRoot.getKey()){
return false;
}
return isEqualChildTree(aRoot.getLeftNode(), bRoot.getLeftNode())&&
isEqualChildTree(aRoot.getRightNode(), bRoot.getRightNode());
}
14、求二叉树中节点的最大距离思路：即二叉树中相距最远的两个节点之间的距离。递归解法：
（1）如果二叉树为空，返回0，同时记录左子树和右子树的深度，都为0
（2）如果二叉树不为空，最大距离要么是左子树中的最大距离，要么是右子树中的最大距离，要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离，同时记录左子树和右子树节点中到根节点的最大距离。
15、将二叉查找树变为有序的双向链表思路：
哈夫曼树—最优二叉树，树的带权路径长度规定为所有叶子结点的带权路径长度之和，带权路径长度最短的树，即为最优二叉树。在最优二叉树中，权值较大的结点离根较近。
首先就需要构建一个哈夫曼树，一般利用优先级队列来构建哈夫曼树
以上面的消息为例，我们先来分析一下构建哈夫曼树的过程，下图中，if代表换行符，sp代表空格
首先，将字符按照频率插入一个优先级队列，频率越低越靠近队头，然后循环执行下面的操作：
1、取出队头的两个树
2、以它们为左右子节点构建一棵新树，新树的权值是两者之和
3、将这棵新树插入队列
直到队列中只有一棵树时，这棵树就是我们需要的哈夫曼树。
java 实现代码如下：
1.哈夫曼树的节点设计
public class Node {
private Node leftNode;
private Node rightNode;
private Node nextNode;
//关键字及其权重
private String key;
private int frequence;
public Node(int frequence,String key){
this.key = key;
this.frequence = frequence;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
public Node getNextNode() {
return nextNode;
}
public void setNextNode(Node nextNode) {
this.nextNode = nextNode;
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public int getFrequence() {
return frequence;
}
public void setFrequence(int frequence) {
this.frequence = frequence;
}
}2.创建哈夫曼树的辅助优先级队列
//优先级队列
public class PriorityQueue {
private Node firstNode;
private int length;
public PriorityQueue(){
firstNode = null;
length = 0;
}
//构造优先级队列（插入元素）
public void insert(Node node){
if(firstNode == null){
firstNode = node;
}else {
Node curNode = firstNode;
Node preNode = null;
//定位要插入节点的前一个和后一个
while(curNode.getFrequence()preNode = curNode;
if(curNode.getNextNode()==null){
//到达队尾
curNode = null;
break;
}else{
//继续向下一个节点查找，直到找到
curNode = curNode.getNextNode();
}
}
if(preNode == null){
//插入到firstNode之前
node.setNextNode(firstNode);
//设置指向新节点node
firstNode = node;
}else if(curNode == null){
//到达队尾，放入preNode之后
preNode.setNextNode(node);
}else {
//插入两个node之间
preNode.setNextNode(node);
node.setNextNode(curNode);
}
}
length++;
}
//取队列头元素
public Node getFirstNode(){
Node tempNode = firstNode;
firstNode = firstNode.getNextNode();
length--;
return tempNode;
}
//求队列深度
public int getLength(){
return length;
}
//按优先级打印队列
public void PrintTree(){
Node curNode = firstNode;
System.out.print("优先级队列：\t");
while (curNode!=null) {
System.out.print(curNode.getKey()+":"+curNode.getFrequence()+"\t");
curNode = curNode.getNextNode();
}
System.out.println();
}
//构建哈夫曼树
public HuffmanTree createHuffmanTree(){
while(length>1){
Node leftNode = getFirstNode();//得到左节点（从优先级队列中取第一个元素：最小权重的元素）
Node rightNode = getFirstNode();//右节点（第二个小权重的元素）
//新节点的权值=左右节点权值之和
Node newNode = new Node((leftNode.getFrequence()+rightNode.getFrequence()),"");
newNode.setLeftNode(leftNode);
newNode.setRightNode(rightNode);
insert(newNode);
}
return new HuffmanTree(firstNode);
}
}
3.哈夫曼树实现类
private Node firstNode;
private Map treeMap = new HashMap();
public HuffmanTree(Node firstNode){
this.firstNode = firstNode;
createHuffmanTree(firstNode, "");
}
//创建哈夫曼编码
private void createHuffmanTree(Node curNode,String curCode){
if(curNode.getKey()!=null&&curNode.getKey()!=""){
//因为哈弗曼树中新添加的节点是没有设置key的，所以一定为叶子节点，添加进去
treeMap.put(curNode.getKey(),curCode);
}else {
//新添加的节点必定存在“左右节点”，
//左右节点递归实现
//转向左子节点需要将当前代码追加0
createHuffmanTree(curNode.getLeftNode(), curCode+"0");
//转向右子节点需要将当前代码追加1
createHuffmanTree(curNode.getRightNode(), curCode+"1");
}
}
//对外提供访问权限
public Map getTreeMap(){
return treeMap;
}
京公网安备 11010802041100号