定义节点类:
public class PTNode { int data; PTNode LeftChild; PTNode RightChild; public PTNode(int data) { this.data = data; this.LeftChild = null; this.RightChild = null; } public int getData() { return data; } public void setData(int data) { this.data = data; } public PTNode getLeftChild() { return LeftChild; } public void setLeftChild(PTNode leftChild) { LeftChild = leftChild; } public PTNode getRightChild() { return RightChild; } public void setRightChild(PTNode rightChild) { RightChild = rightChild; } }
一 求二叉树的最大深度:根节点到最远叶子结点的距离
int getMaxDeath(PTNode root) { if(null == root) { return 0; } int left = getMaxDeath(root.LeftChild); int right = getMaxDeath(root.RightChild); return Math.max(left, right)+1; }
二 求二叉树的最小深度:根节点到最近叶子结点的距离
int getMinDepth(PTNode root) { if(null == root) { return 0; } if(null == root.LeftChild) { return getMinDepth(root.RightChild)+1; } if(null == root.RightChild) { return getMinDepth(root.LeftChild)+1; } int left = getMaxDeath(root.LeftChild)+1; int right = getMaxDeath(root.RightChild)+1; return Math.min(left, right); }
三 求二叉树的节点个数
int getNumOfTreeNode(PTNode root) { if(null == root) { return 0; } return getNumOfTreeNode(root.LeftChild)+getNumOfTreeNode(root.RightChild)+1; }
四 求二叉树叶子节点个数
int getNumOfChildNode(PTNode root) { if(null == root) { return 0; } if(null == root.LeftChild && null == root.RightChild) { return 1; } return getNumOfChildNode(root.LeftChild)+getNumOfChildNode(root.RightChild); }
五 求二叉树中第k层节点的个数
int getNumOfLevelNode(PTNode root,int k) { if(null == root || k<1) { return 0; } if(1 == k) { return 1; } int numleft = getNumOfLevelNode(root.LeftChild,k-1); int numright = getNumOfLevelNode(root.RightChild,k-1); return numleft + numright; }
六 判断二叉树是否为平衡二叉树
对于每一个节点,它的右子树深度减去左子树的深度的绝对值必须小于2
boolean isBalancedTree(PTNode root) { if(null == root) { return true; } int left = getMaxDeath(root.LeftChild); int right = getMaxDeath(root.RightChild); if(Math.abs(left-right) > 1) { return false; } return isBalancedTree(root.LeftChild) && isBalancedTree(root.RightChild); }
七 判断是否为完全二叉树
除第h层外其他各层的节点数都达到最大个数,且第h层所有的节点都连续集中在最左边
boolean isCompleteTree(PTNode root) { if(null == root) { return false; } Queue<PTNode> queue = new LinkedList<PTNode>(); queue.add(root); boolean result = true; boolean hasChild = true; while(!queue.isEmpty()) { PTNode currentNode = queue.remove(); if(!hasChild) {//没有叶子节点 if(null != currentNode.LeftChild || null != currentNode.RightChild) { result = false; break; } }else {//有叶子节点 if(null != currentNode.LeftChild && null != currentNode.RightChild) { queue.add(currentNode.LeftChild); queue.add(currentNode.RightChild); }else if(null != currentNode.LeftChild && null == currentNode.RightChild) { queue.add(currentNode.LeftChild); hasChild = false; }else if(null == currentNode.LeftChild && null != currentNode.RightChild) { result = false; break; }else { hasChild = false; } } } return result; }
八 判断两个二叉树是否相等
boolean isSameTree(PTNode t1,PTNode t2) { if(null == t1 && null == t2) { return true; }else if(null == t1 || null == t2) { return false; } if(t1.data != t2.data) { return false; } return isSameTree(t1.LeftChild,t2.LeftChild)&&isSameTree(t1.RightChild,t2.RightChild); }
九 判断两个二叉树是否为镜像
boolean isMirrorTree(PTNode t1,PTNode t2) { if(null == t1 && null == t2) { return true; }else if(null == t1 || null == t2) { return false; } if(t1.data != t2.data) { return false; } return isMirrorTree(t1.LeftChild,t2.RightChild)&&isMirrorTree(t1.RightChild,t2.LeftChild); }
十 翻转二叉树(镜像二叉树)
PTNode mirrorTree(PTNode root) { if(null == root) { return null; } PTNode left = mirrorTree(root.LeftChild); PTNode right = mirrorTree(root.RightChild); root.LeftChild = left; root.RightChild = right; return root; }
十一 二叉树的前序遍历
void PreOrderTraverse(PTNode root,ArrayList<Integer> result) { if(null == root) { return ; } result.add(root.data); System.out.print(root.data + " "); PreOrderTraverse(root.LeftChild,result); PreOrderTraverse(root.RightChild,result); }
十二 二叉树的中序遍历
void InOrderTraverse(PTNode root,ArrayList<Integer> result) { if(null == root) { return ; } InOrderTraverse(root.LeftChild,result); result.add(root.data); System.out.print(root.data + " "); InOrderTraverse(root.RightChild,result); }十三 二叉树的后序遍历
void PostOrderTraverse(PTNode root,ArrayList<Integer> result) { if(null == root) { return ; } PostOrderTraverse(root.LeftChild,result); PostOrderTraverse(root.RightChild,result); result.add(root.data); System.out.print(root.data + " "); }
十四 二叉树的层次遍历
先将根节点入队,当前节点是队头节点,将其出队并访问,如果当前节点的左节点不为空将左节点入队,如果当前节点的右节点不为空将其入队。所以出队顺序也是从左到右依次出队。
ArrayList<ArrayList<Integer>> levelOrderTree(PTNode root) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if(null == root) { return result; } Queue<PTNode> queue = new LinkedList<PTNode>(); PTNode current = null; queue.offer(root); while(!queue.isEmpty()) { int size = queue.size(); ArrayList<Integer> arr = new ArrayList<Integer>(); for(int i=0;i<size;i++) { current = queue.poll(); arr.add(current.data); if(current.LeftChild != null) { queue.offer(current.LeftChild); } if(current.RightChild != null) { queue.offer(current.RightChild); } } result.add(arr); } return result; }
十五 判断二叉树是否是合法的二叉查找树(BST)
一棵BST定义为:
* 节点的左子树中的值要严格小于该节点的值。
* 节点的右子树中的值要严格大于该节点的值。
* 左右子树也必须是二叉查找树。
* 一个节点的树也是二叉查找树。
boolean isValidBST(PTNode root,long minVal,long maxVal) { if(null == root) { return true; } if(root.data >= maxVal || root.data <=minVal) { return false; } return isValidBST(root.LeftChild,minVal,root.data)&&isValidBST(root.RightChild,root.data,maxVal); }
十六 创建二叉树
* 已知前序遍历和中序遍历可以唯一确定一颗二叉树
* 已知后序遍历和中序遍历可以唯一确定一颗二叉树
* 已知中序遍历和后序遍历不能唯一确定一颗二叉树
void createBinaryTree(int[] datas,List<PTNode>nodelist) { for(int nodeindex=0;nodeindex<datas.length;nodeindex++) { PTNode node = new PTNode(datas[nodeindex]); nodelist.add(node); } for(int index=0;index<nodelist.size()/2-1;index++) { //编号为n的节点他的左子节点编号为2*n 右子节点编号为2*n+1 但是因为list从0开始编号 nodelist.get(index).setLeftChild(nodelist.get(index*2+1)); nodelist.get(index).setRightChild(nodelist.get(index*2+2)); } int index = nodelist.size()/2-1; nodelist.get(index).setLeftChild(nodelist.get(index*2+1)); if(nodelist.size()%2 == 1) { nodelist.get(index).setRightChild(nodelist.get(index*2+2)); } }参考博客:https://www.jianshu.com/p/0190985635eb