package com.xk.test.struct.newp; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class MyBinaryTree { /** * 插入节点 * @param root * @param node * @return */ TreeNode insertNode(TreeNode root,TreeNode node){ if(root == node){ return node; } TreeNode tmp = new TreeNode(); tmp = root; TreeNode last = null; while(tmp!=null){ last = tmp; if(tmp.val>node.val){ tmp = tmp.left; }else{ tmp = tmp.right; } } if(last!=null){ if(last.val>node.val){ last.left = node; }else{ last.right = node; } } return root; } /** * 递归解法前序遍历 * @param root * @return */ ArrayList<Integer> preOrderReverse(TreeNode root){ ArrayList<Integer> result = new ArrayList<Integer>(); preOrder2(root,result); return result; } void preOrder2(TreeNode root,ArrayList<Integer> result){ if(root == null){ return; } result.add(root.val); preOrder2(root.left,result); preOrder2(root.right,result); } /** * 迭代解法前序遍历 * @param root * @return */ ArrayList<Integer> preOrder(TreeNode root){ Stack<TreeNode> stack = new Stack<TreeNode>(); ArrayList<Integer> list = new ArrayList<Integer>(); if(root == null){ return list; } stack.push(root); while(!stack.empty()){ TreeNode node = stack.pop(); list.add(node.val); if(node.right!=null){ stack.push(node.right); } if(node.left != null){ stack.push(node.left); } } return list; } /** * 中序遍历 * @param root * @return */ ArrayList<Integer> inOrder(TreeNode root){ ArrayList<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode current = root; while(current != null|| !stack.empty()){ while(current != null){ stack.add(current); current = current.left; } current = stack.peek(); stack.pop(); list.add(current.val); current = current.right; } return list; } /** * 后序遍历 * @param root * @return */ ArrayList<Integer> postOrder(TreeNode root){ ArrayList<Integer> list = new ArrayList<Integer>(); if(root == null){ return list; } list.addAll(postOrder(root.left)); list.addAll(postOrder(root.right)); list.add(root.val); return list; } /** * 最大深度 * @param node * @return */ int maxDeath(TreeNode node){ if(node==null){ return 0; } int left = maxDeath(node.left); int right = maxDeath(node.right); return Math.max(left,right) + 1; } /** * 层次遍历 * @param root * @return */ ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){ ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if(root == null){ return result; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); ArrayList<Integer> level = new ArrayList<Integer>(); for(int i = 0;i < size ;i++){ TreeNode node = queue.poll(); level.add(node.val); if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); } } result.add(level); } return result; } /** * 最小深度 * @param root * @return */ int getMinDepth(TreeNode root){ if(root == null){ return 0; } return getMin(root); } int getMin(TreeNode root){ if(root == null){ return Integer.MAX_VALUE; } if(root.left == null&&root.right == null){ return 1; } return Math.min(getMin(root.left),getMin(root.right)) + 1; } /** * 节点的个数 * @param root * @return */ int numOfTreeNode(TreeNode root){ if(root == null){ return 0; } int left = numOfTreeNode(root.left); int right = numOfTreeNode(root.right); return left + right + 1; } /** * 叶子节点的个数 * @param root * @return */ int numsOfNodeTreeNode(TreeNode root){ if(root == null){ return 0; } if(root.left==null&&root.right==null){ return 1; } return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right); } /** * 第k层节点的个数 * @param root * @param k * @return */ int numsOfkLevelTreeNode(TreeNode root,int k){ if(root == null||k<1){ return 0; } if(k==1){ return 1; } int numsLeft = numsOfkLevelTreeNode(root.left,k-1); int numsRight = numsOfkLevelTreeNode(root.right,k-1); return numsLeft + numsRight; } /** * 翻转二叉树or镜像二叉树 * @param root * @return */ TreeNode mirrorTreeNode(TreeNode root){ if(root == null){ return null; } TreeNode left = mirrorTreeNode(root.left); TreeNode right = mirrorTreeNode(root.right); root.left = right; root.right = left; return root; } /** * 两个二叉树是否互为镜像 * @param t1 * @param t2 * @return */ boolean isMirror(TreeNode t1,TreeNode t2){ if(t1==null&&t2==null){ return true; } if(t1==null||t2==null){ return false; } if(t1.val != t2.val){ return false; } return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left); } /** * 是否是平衡二叉树 * 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 * @param node * @return */ boolean isBalanced(TreeNode node){ return maxDeath2(node)!=-1; } int maxDeath2(TreeNode node){ if(node == null){ return 0; } int left = maxDeath2(node.left); int right = maxDeath2(node.right); if(left==-1||right==-1||Math.abs(left-right)>1){ return -1; } return Math.max(left, right) + 1; } /** * 是否是完全二叉树 * 对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 * @param root * @return */ boolean isCompleteTreeNode(TreeNode root){ if(root == null){ return false; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); boolean result = true; boolean hasNoChild = false; while(!queue.isEmpty()){ TreeNode current = queue.remove(); if(hasNoChild){ if(current.left!=null||current.right!=null){ result = false; break; } }else{ if(current.left!=null&¤t.right!=null){ queue.add(current.left); queue.add(current.right); }else if(current.left!=null&¤t.right==null){ queue.add(current.left); hasNoChild = true; }else if(current.left==null&¤t.right!=null){ result = false; break; }else{ hasNoChild = true; } } } return result; } /** * 是否是合法的二叉查找树(BST) 一棵BST定义为: 节点的左子树中的值要严格小于该节点的值。 节点的右子树中的值要严格大于该节点的值。 左右子树也必须是二叉查找树。 一个节点的树也是二叉查找树。 */ public int lastVal = Integer.MAX_VALUE; public boolean firstNode = true; public boolean isValidBST(TreeNode root) { // write your code here if(root==null){ return true; } if(!isValidBST(root.left)){ return false; } if(!firstNode&&lastVal >= root.val){ return false; } firstNode = false; lastVal = root.val; if (!isValidBST(root.right)) { return false; } return true; } /** * 把二叉树打印成多行 * @param pRoot * @return */ ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >(); if(pRoot == null) return res; ArrayList<Integer> temp = new ArrayList<Integer>(); Queue<TreeNode> layer = new LinkedList<TreeNode>(); layer.offer(pRoot); int start = 0, end = 1; while(!layer.isEmpty()){ TreeNode node = layer.poll(); temp.add(node.val); start ++; if(node.left != null) layer.add(node.left); if(node.right != null) layer.add(node.right); if(start == end){ start = 0; res.add(temp); temp = new ArrayList<Integer>(); end = layer.size(); } } return res; } /** * 按之字形顺序打印二叉树 * @param pRoot * @return */ public ArrayList<ArrayList<Integer> > PrintZ(TreeNode pRoot) { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >(); Stack<TreeNode> s1 = new Stack<TreeNode>(); Stack<TreeNode> s2 = new Stack<TreeNode>(); int flag = 1; if(pRoot == null) return res; s2.push(pRoot); ArrayList<Integer> temp = new ArrayList<Integer>(); while(!s1.isEmpty() || !s2.isEmpty()){ if(flag % 2 != 0){ while(!s2.isEmpty()){ TreeNode node = s2.pop(); temp.add(node.val); if(node.left != null){ s1.push(node.left); } if(node.right != null){ s1.push(node.right); } } } if(flag % 2 == 0){ while(!s1.isEmpty()){ TreeNode node = s1.pop(); temp.add(node.val); if(node.right != null){ s2.push(node.right); } if(node.left != null){ s2.push(node.left); } } } res.add(new ArrayList<Integer>(temp)); temp.clear(); flag ++; } return res; } } class TreeNode{ int val; //左孩子 TreeNode left; //右孩子 TreeNode right; }
转自:https://www.jianshu.com/p/0190985635eb
https://www.weiweiblog.cn/printz/