preorder
public void preOrderTraverse1(TreeNode root) {
if (root != null) {
System.out.print(root.val + "->");
preOrderTraverse1(root.left);
preOrderTraverse1(root.right);
}
}
inorder
public void inOrderTraverse(TreeNode root) {
if (root != null ) {
inOrderTraverse(root. left);
System.out.print(root.val + "->" );
inOrderTraverse(root.right);
}
}
postorder
public void inOrderTraverse(TreeNode root) {
if(root!=null){
inOrderTraverse(root.left);
inOrderTraverse(root.right);
System.out.println(root.val+"->");
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length==0||inorder.length==0){
return null;
}
int preL=0,preR=preorder.length-1;
int inL=0,inR=inorder.length-1;
return createTree(preorder,inorder,preL,preR,inL,inR);
}
public TreeNode createTree(int[] preorder, int[] inorder,int preL,int preR,int inL,int inR){
if(preL>preR){
return null;
}
TreeNode root=new TreeNode(preorder[preL]);
int k=0;
for(int i=0;i<inorder.length;i++){
if(inorder[i]==root.val){
k=i;
break;
}
}
int numleft=k-inL;
root.left=createTree(preorder,inorder,preL+1,preL+numleft,inL,k-1);
root.right=createTree(preorder,inorder,preL+numleft+1,preR, k+1, inR);
return root;
}
}
postorder && inorder
root.left=createTree(postL,postL+numleft-1,inL,k-1);
root.right=createTree(postL+numleft,postR-1, k+1,inR);
