中序遍历后序遍历 构建二叉树

/**
 * Definition for binary tree public class TreeNode { int val; TreeNode left;
 * TreeNode right; TreeNode(int x) { val = x; } }
 */
public class Solution {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		if (inorder == null || postorder == null || inorder.length != postorder.length)
			return null;
		int n = inorder.length;
		return buildTree(inorder, postorder, 0, n - 1, 0, n - 1);
	}

	// 根据中序遍历和后序遍历生成二叉树 dfs
	public TreeNode buildTree(int[] inorder, int[] postorder, int s1, int e1, int s2, int e2) {
		if (s1 > e1 || s2 > e2)
			return null;
		if (s2 == e2)
			return new TreeNode(postorder[s2]);

		// 后序遍历数组的最后一个是根节点
		int rootval = postorder[e2];
		TreeNode root = new TreeNode(rootval);
		int i;

		// 根据根节点在中序遍历数组里面得到左子树和右子数节点的数目
		for (i = s1; i <= e1; i++) {
			if (inorder[i] == rootval)
				break;
		}
		int leftlength = i - s1;
		int rightlength = e1 - i;

		// dfs递归
		root.left = buildTree(inorder, postorder, s1, i - 1, s2, s2 + leftlength - 1);
		root.right = buildTree(inorder, postorder, i + 1, e1, e2 - rightlength, e2 - 1);
		return root;
	}

	public int getlength(TreeNode root) {
		int depthLeft = 0;
		int depthRight = 0;
		int depth = 0;

		// 左子树的深度
		if (root.left != null) {
			depthLeft = getlength(root.left) + 1;
		}

		// 右子树的深度
		if (root.right != null) {
			depthRight = getlength(root.right) + 1;
		}
		if (depthLeft >= depthRight) {
			depth = depthLeft;
		} else {
			depth = depthRight;
		}
		return depth;
	}

	public static void main(String[] args) {
		String in = "T,b,H,V,h,3,o,g,P,W,F,L,u,A,f,G,r,m,1,x,J,7,w,e,0,i,Q,Y,n,Z,8,K,v,q,k,9,y,5,C,N,B,D,2,4,U,l,c,p,I,E,M,a,j,6,S,R,O,X,s,d,z,t";
		String po = "T,V,H,o,3,h,P,g,b,F,f,A,u,m,r,7,J,x,e,w,1,Y,Q,i,0,Z,n,G,L,K,y,9,k,q,v,N,D,B,C,5,4,c,l,U,2,8,E,I,R,S,6,j,d,s,X,O,a,M,p,W,t,z";
		String[] inChar = in.split(",");
		String[] poChar = po.split(",");
		System.out.println(inChar.length);
		System.out.println(poChar.length);

		int[] inI = new int[inChar.length];
		int[] poI = new int[poChar.length];
		for (int i = 0; i < inChar.length; i++) {
			inI[i] = inChar[i].toCharArray()[0];
			poI[i] = poChar[i].toCharArray()[0];
		}

		TreeNode tree = new Solution().buildTree(inI, poI);

		System.out.println(new Solution().getlength(tree));

		// for(int i=0;i<inChar.length;i++){
		// System.out.print(inI[i]+" ");
		// }
		// System.out.println();
		// for(int i=0;i<inChar.length;i++){
		// System.out.print(poI[i]+" ");
		// }

	}

}

// Definition for binary tree
class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}

}