二叉树特性：
image.png
二叉树 - 图2
前序排列：1、3、6、5、2、4
中序排列：6、3、5、1、2、4
后序排列：6、5、3、4、2、1
层序排列：1、3、2、6、5、4

根据前序和中序还原二叉树(后序中序同理)

  1. //根据前序节点得到root节点
  2. //循环从中序中root节点的下标i找到
  3. //左节点=把中序从0到i，前序从1到i+1放到方法中递归
  4. //右节点=把中序从i+1到中序最后，前序从i+1到前序最后
  6. public static TreeNode reConstruct_PreMid(int[] preOrder, int[] midOrder) {
  7.     if (preOrder.length == 0 || midOrder.length == 0) {
  8.         return null;
  9.     }
  10.     // preOrder[0] 必定是root根节点
  11.     TreeNode root = new TreeNode(preOrder[0]);
  12.     for (int i = 0; i < midOrder.length; i++) {
  13.         if (preOrder[0] == midOrder[i]) {
  14.             root.leftChild = reConstruct_PreMid(Arrays.copyOfRange(preOrder, 1, i + 1),
  15.                     Arrays.copyOfRange(midOrder, 0, i));
  16.             root.rightChild = reConstruct_PreMid(Arrays.copyOfRange(preOrder, i + 1, preOrder.length),
  17.                     Arrays.copyOfRange(midOrder, i + 1, midOrder.length));
  18.         }
  19.     }
  20.     return root;
  21. }

根据层序和中序还原二叉树

  1. //根据层序第一个节点是root节点找出mid中root节点的下标i
  2. //如果层序的长度大于2，就进行下一步，否则返回root节点
  3. //判断层序第二个节点是左子树还是右子树（）
  4. //如果为左子树，
  5.     //左节点=获取层序数列中左子树的层序，再递归执行
  6.     //右节点=如果层序len大于等于3，且层序第三个节点为右节点，则获取右节点层序，递归执行
  7. //如果为右子树，则获取右子树的层序，递归执行
  9. //判断左子树：循环中序，如果等于root节点值就返回，如果等于目标节点则标志为左节点
  10. //获取子层序：中序根据root节点，传入左或者右节点序列，再根据原层序一一比对，找出相同的则为子层序
  11. public static TreeNode buildTreeByMidLevel(int[] levelOrder, int[] midOrder, int midBegin, int midEnd) {
  12.     if (levelOrder.length == 0 || midOrder.length == 0) {
  13.         return null;
  14.     }
  15.     // levelOrder[0] 必定是root根节点
  16.     TreeNode root = new TreeNode(levelOrder[0]);
  17.     // rootLocation：（子）序列中根节点的位置
  18.     int rootLocation = -1;
  19.     for (int i = midBegin; i <= midEnd; i++) {
  20.         if (midOrder[i] == levelOrder[0]) {
  21.             rootLocation = i;
  22.             break;
  23.         }
  24.     }
  25.     // 划分左右子树
  26.     // levelOrder.length会影响划分
  27.     if (levelOrder.length >= 2) {
  28.         if (isLeft(midOrder, levelOrder[0], levelOrder[1])) {
  29.             // 左子树
  30.             root.leftChild = buildTreeByMidLevel(getLevelStr(midOrder, midBegin, rootLocation - 1, levelOrder),
  31.                     midOrder, midBegin, rootLocation - 1);
  32.             // 处理左子树为空的情况,注意levelOrder.length需>=3
  33.             if (levelOrder.length >= 3 && !isLeft(midOrder, levelOrder[0], levelOrder[2])) {
  34.                 root.rightChild = buildTreeByMidLevel(getLevelStr(midOrder, rootLocation + 1, midEnd, levelOrder),
  35.                         midOrder, rootLocation + 1, midEnd);
  36.             }
  37.         } else {
  38.             // 右子树
  39.             root.rightChild = buildTreeByMidLevel(getLevelStr(midOrder, rootLocation + 1, midEnd, levelOrder),
  40.                     midOrder, rootLocation + 1, midEnd);
  41.         }
  42.     }
  43.     return root;
  44. }
  46. public static boolean isLeft(int[] order, int root, int child) {
  47.     boolean findVal = false;
  48.     for (int temp : order) {
  49.         if (temp == child) {
  50.             findVal = true;
  51.         } else if (temp == root) {
  52.             return findVal;
  53.         }
  54.     }
  55.     return false;
  56. }
  58. public static int[] getLevelStr(int[] midOrder, int midBegin, int midEnd, int[] levelOrder) {
  59.     int[] result = new int[midEnd - midBegin + 1];
  60.     int curLoc = 0;
  61.     for (int i = 0; i < levelOrder.length; i++) {
  62.         if (contains(midOrder, levelOrder[i], midBegin, midEnd)) {
  63.             result[curLoc++] = levelOrder[i];
  64.         }
  65.     }
  66.     return result;
  67. }
  69. public static boolean contains(int[] midOrder, int target, int midBegin, int midEnd) {
  70.     for (int i = midBegin; i <= midEnd; i++) {
  71.         if (midOrder[i] == target) {
  72.             return true;
  73.         }
  74.     }
  75.     return false;
  76. }

找出每层最大值

  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.Queue;
  5. public class Main {
  7.     public static class TreeNode {
  8.         public int val;
  9.         public TreeNode left;
  10.         public TreeNode right;
  12.         public TreeNode(int data) {
  13.             this.val = data;
  14.         }
  15.     }
  17.     //找出二叉树每层的最大值节点
  18.     public static void findMaxNodeInLevel(TreeNode pRoot) {
  19.         ArrayList<Integer> resultList = new ArrayList<>();
  20.         Queue<TreeNode> layer = new LinkedList<TreeNode>();
  21.         ArrayList<Integer> layerList = new ArrayList<Integer>();
  22.         layer.add(pRoot);
  23.         int start = 0, end = 1;
  24.         while (!layer.isEmpty()) {
  25.             TreeNode cur = layer.remove();
  26.             layerList.add(cur.val);
  27.             start++;
  28.             if (cur.left != null) {
  29.                 layer.add(cur.left);
  30.             }
  31.             if (cur.right != null) {
  32.                 layer.add(cur.right);
  33.             }
  34.             if (start == end) {
  35.                 end = layer.size();
  36.                 start = 0;
  37.                 resultList.add(findMaxNode(layerList));
  38.                 layerList = new ArrayList<Integer>();
  39.             }
  40.         }
  41.         for (Integer i : resultList) {
  42.             System.out.println(i);
  43.         }
  44.     }
  46.     public static int findMaxNode(ArrayList<Integer> list) {
  47.         int max = Integer.MIN_VALUE;
  48.         for (Integer i : list) {
  49.             if (max < i) {
  50.                 max = i;
  51.             }
  52.         }
  53.         return max;
  54.     }
  56.     public static void main(String[] args) {
  57.         TreeNode head = new TreeNode(1);
  58.         head.left = new TreeNode(2);
  59.         head.right = new TreeNode(3);
  60.         head.left.left = new TreeNode(4);
  61.         head.left.right = new TreeNode(5);
  62.         head.right.left = new TreeNode(6);
  63.         head.right.right = new TreeNode(7);
  64.         findMaxNodeInLevel(head);
  65.     }
  66. }

求最大宽度

  1. public static int getMaxWidth2(Node head) {
  2.     if (head == null) {
  3.         return 0;
  4.     }
  5.     //当前层最后一个结点
  6.     Node curEnd = head;
  7.     //下一层最后一个结点
  8.     Node nextEnd = null;
  9.     //当前层结点数
  10.     int curLevelNodes = 0;
  11.     //结点数最多的层的结点数
  12.     int max = Integer.MIN_VALUE;
  13.     Queue<Node> queue = new LinkedList<>();
  14.     queue.add(head);
  15.     while (!queue.isEmpty()) {
  16.         head = queue.poll();
  17.         curLevelNodes++;
  18.         if (head.left != null) {
  19.             queue.add(head.left);
  20.             nextEnd = head.left;
  21.         }
  22.         if (head.right != null) {
  23.             queue.add(head.right);
  24.             nextEnd = head.right;
  25.         }
  26.         if (head == curEnd) {
  27.             max = Math.max(max, curLevelNodes);
  28.             curLevelNodes = 0;
  29.             curEnd = nextEnd;
  30.             nextEnd = null;
  31.         }
  32.     }
  33.     return max;
  34. }