二叉树--算法题总结

1、利用层序遍历的产生的字符串来创建二叉树

 /*** 使用层序遍历的字符串创建二叉树* @param treeInfo* @return*/public static TreeNode generateTreeNodeSecond(String treeInfo) {LinkedList<TreeNode> treeNodeLinkedList = new LinkedList<>();if(StringUtils.isEmpty(treeInfo)) {return null;}String[] stringList = treeInfo.split(",");int i =0;TreeNode root = new TreeNode(Integer.valueOf(stringList[i]));treeNodeLinkedList.offer(root);i++;while(!treeNodeLinkedList.isEmpty()) {TreeNode currentNode = treeNodeLinkedList.poll();String  temp = stringList[i];if(temp.compareTo("null")!=0) {currentNode.left = new TreeNode(Integer.valueOf(temp));treeNodeLinkedList.offer(currentNode.left);}i++;temp = stringList[i];if(temp.compareTo("null")!=0) {currentNode.right = new TreeNode(Integer.valueOf(temp));treeNodeLinkedList.offer(currentNode.right);}i++;if(i>= stringList.length) {break;}}return root;}

2、层序遍历二叉树

public static List<List<Integer>> levelShow(TreeNode root) {List<List<Integer>> listList = new ArrayList<>();LinkedList<TreeNode> treeNodeLinkedList = new LinkedList<>();treeNodeLinkedList.offer(root);while(!treeNodeLinkedList.isEmpty()) {int size = treeNodeLinkedList.size();List<Integer> rowInfo = new ArrayList<>();for(int i =0;i< size;i++) {TreeNode treeNode = treeNodeLinkedList.poll();// 读取数据rowInfo.add(treeNode.value);if(treeNode.left !=null) {treeNodeLinkedList.offer(treeNode.left);}if(treeNode.right !=null) {treeNodeLinkedList.offer(treeNode.right);}}listList.add(rowInfo);}return listList;}

3、获取树中节点的个数

    /*** 获取树中节点的个数* @param root* @return*/public int size(TreeNode root) {if(root == null) {return 0;}//递归遍历左子树int a = size(root.left);int b= size(root.right);return a + b+ 1;}

4、获取叶子节点的个数

   /*** 获取叶子节点的个数* @param root* @return*/public int getLeaf(TreeNode root) {if(root == null)  {return 0;}if(root.left == null &&root.right == null) {// 判断叶子左右节点是否为空，若为空则为叶子节点return 1;}int getLeafLeft = getLeaf(root.left);int getLeafRight = getLeaf(root.right);return getLeafLeft + getLeafRight;}

5、获取第k层的节点个数

/*** 获取第k层的节点个数* @param root* @param k* @return*/public static int getKLevelNode(TreeNode root,int k) {if(root == null) {return 0;}if(k == 1) {return 1;}int getKLevelNodeLeft =  getKLevelNode(root.left , k-1);int getKLevelNodeRight = getKLevelNode(root.right , k -1);return getKLevelNodeLeft +getKLevelNodeRight;}

6、查询对应值的节点

    public static TreeNode find(TreeNode root, int val) {if(root == null) {return null;}if(root.value == val) {return root;}// 左子树查找val 使用对应的值TreeNode leftTree = find(root.left, val);// 接收值不为 null ,说明左子树已经查找到valif(leftTree != null) {return leftTree;}// 右子树查找val, 使用 rightTree 来接收TreeNode rightTree = find(root.right ,val);if(rightTree !=null) {return rightTree;}// 走到这一步说明左右子树都没有找到val,直接返回nullreturn null;}

7、是否是完全二叉树

public static boolean isCompleteTree(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();queue.offer(root);boolean isStep1 = true;while(!queue.isEmpty()) {TreeNode node = queue.poll();if(isStep1) {if(node.left !=null && node.right != null) {queue.offer(node.left);queue.offer(node.right);} else if(node.left  !=null){queue.offer(node.left);isStep1 = false;} else if(node.right !=null) {return false;}  else {isStep1 = false;}} else {// 到达第二轮的时候，如果两者存在一个为空的就说明不是完全二叉树if(node.left!=null || node.right !=null) {return false;}}}return true;}

8、两棵树是否完全相同

    /*** 检查两颗树是否相同* @param p* @param q* @return*/public static boolean isSameTree(TreeNode p, TreeNode q) {if( p== null&&  q== null) {return true;}if ( p == null || q == null) {return false;}if(p.value == q.value) {return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}return false;}

9、一颗树是否是另一个树的子树

    /*** 判断是否是子树* @param root* @param subRoot* @return*/public static boolean isSubTree(TreeNode root ,TreeNode subRoot) {if(subRoot == null) {return true;}if(root == null) {return false;}// 递归判断return isSameTree(root,subRoot) || isSubTree(root.left,subRoot) ||isSubTree(root.right,subRoot);}

10、打印从根节点到子节点的路径

 /*** 打印对应根节点到子节点的路径* @param root*/public  static void showTrace(TreeNode root) {List<String> result = new ArrayList<>();// 声明一个队列LinkedList<TreeNode> queue = new LinkedList<>();// 记录路径信息LinkedList<String> stringLinkedList = new LinkedList<>();queue.offer(root);stringLinkedList.offer(root.value + "");while(queue !=null) {TreeNode tempNode =queue.poll();String currentPath = stringLinkedList.poll();// 说明不是子节点if(tempNode.left == null && tempNode.right == null) {result.add(currentPath);}if(tempNode.left  != null) {queue.offer(tempNode.left);stringLinkedList.offer(currentPath + "->" + tempNode.left.value);}if(tempNode.right !=null) {queue.offer(tempNode.right);stringLinkedList.offer(currentPath + "->" + tempNode.right.value);}}for(String item: result) {System.out.println(item);}}