本文共 4271 字，大约阅读时间需要 14 分钟。
public class GetTreeNodeNumber { public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } public static int nodeNum(Node head) { if (head == null) { return 0; } return bs(head, 1, mostLeftLevel(head, 1)); } public static int bs(Node node, int l, int h) { if (l == h) { return 1; } if (mostLeftLevel(node.right, l + 1) == h) { return (1 << (h - l)) + bs(node.right, l + 1, h); } else { return (1 << (h - l - 1)) + bs(node.left, l + 1, h); } } public static int mostLeftLevel(Node node, int level) { while (node != null) { level++; node = node.left; } return level - 1; } public static void main(String[] args) { Node head = new Node(1); head.left = new Node(2); head.right = new Node(3); head.left.left = new Node(4); head.left.right = new Node(5); head.right.left = new Node(6); System.out.println(nodeNum(head)); }} public class PreAndInArrayToPosArray { public static int[] getPosArray(int[] pre, int[] in) { if (pre == null || in == null) { return null; } int len = pre.length; int[] pos = new int[len]; HashMap map = new HashMap (); for (int i = 0; i < len; i++) { map.put(in[i], i); } setPos(pre, 0, len - 1, in, 0, len - 1, pos, len - 1, map); return pos; } public static int setPos(int[] p, int pi, int pj, int[] n, int ni, int nj, int[] s, int si, HashMap map) { if (pi > pj) { return si; } s[si--] = p[pi]; int i = map.get(p[pi]); si = setPos(p, pj - nj + i + 1, pj, n, i + 1, nj, s, si, map); return setPos(p, pi + 1, pi + i - ni, n, ni, i - 1, s, si, map); } public static void main(String[] args) { int[] pre = { 1, 2, 4, 5, 3, 6, 7 }; int[] in = { 4, 2, 5, 1, 6, 3, 7 }; int[] pos = getPosArray(pre, in); for(int i=0;i public class ErgtoTree { public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } public static Node preintoTree(int[] pre,int[] in) { if (pre==null || in==null) { return null; } HashMap hashMap = new HashMap<>(); for(int i=0;i hashMap) { if (pi>pj) { return null; } Node root = new Node(p[pi]); int index = hashMap.get(p[pi]); root.left = prein(p, pi+1,pi+index-ni, n, ni,index-1, hashMap); root.right = prein(p, pi+index-ni+1, pj, n, index+1, nj, hashMap); return root; } public static void prePrint(Node root) { if (root==null) { return; } System.out.print(root.value+" "); prePrint(root.left); prePrint(root.right); } public static Node inPosToTree(int[] in, int[] pos) { if (in == null || pos == null) { return null; } HashMap map = new HashMap (); for (int i = 0; i < in.length; i++) { map.put(in[i], i); } return inPos(in, 0, in.length - 1, pos, 0, pos.length - 1, map); } public static Node inPos(int[] n, int ni, int nj, int[] s, int si, int sj, HashMap map) { if (si > sj) { return null; } Node head = new Node(s[sj]); int index = map.get(s[sj]); head.left = inPos(n, ni, index - 1, s, si, si + index - ni - 1, map); head.right = inPos(n, index + 1, nj, s, si + index - ni, sj - 1, map); return head; } public static Node prePosToTree(int[] pre, int[] pos) { if (pre == null || pos == null) { return null; } HashMap map = new HashMap (); for (int i = 0; i < pos.length; i++) { map.put(pos[i], i); } return prePos(pre, 0, pre.length - 1, pos, 0, pos.length - 1, map); } public static Node prePos(int[] p, int pi, int pj, int[] s, int si, int sj, HashMap map) { Node head = new Node(s[sj--]); if (pi == pj) { return head; } int index = map.get(p[++pi]); head.left = prePos(p, pi, pi + index - si, s, si, index, map); head.right = prePos(p, pi + index - si + 1, pj, s, index + 1, sj, map); return head; } public static void main(String[] args) { int[] pre = { 1, 2, 4, 5, 8, 9, 3, 6, 7 }; int[] in = { 4, 2, 8, 5, 9, 1, 6, 3, 7 }; int[] pos = { 4, 8, 9, 5, 2, 6, 7, 3, 1 }; Node root1 = preintoTree(pre, in); prePrint(root1); System.out.println(); Node root2 = inPosToTree(in, pos); prePrint(root2); System.out.println(); Node root3 = prePosToTree(pre, pos); prePrint(root3); }} 转载地址：http://pvcqb.baihongyu.com/