剑指Offer之Java算法习题精讲二叉树的构造和遍历

/**

  * 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 constructMaximumBinaryTree( int [] nums) {

         return method(nums, 0 ,nums.length- 1 );

     }

     public TreeNode method( int [] nums, int lo, int hi){

         if (lo>hi){

             return null ;

         }

         int index = - 1 ;

         int max = Integer.MIN_VALUE;

         for ( int i = lo;i<=hi;i++){

             if (max<nums[i]){

                 max = nums[i];

                 index = i;

             }

         }

         TreeNode root = new TreeNode(max);

         root.left = method(nums,lo,index- 1 );

         root.right = method(nums,index+ 1 ,hi);

         return root;

     }

}

/**

  * 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) {

         return method(preorder, 0 ,preorder.length- 1 ,inorder, 0 ,inorder.length- 1 );

     }

     public TreeNode method( int [] preorder, int preLeft, int preEnd , int [] inorder, int inLeft, int inEnd){

         if (preLeft>preEnd){

             return null ;

         }

         int rootVal = preorder[preLeft];

         int index = - 1 ;

         for ( int i = inLeft;i<=inEnd;i++){

             if (rootVal == inorder[i]){

                 index = i;

             }

         }

         TreeNode root = new TreeNode(rootVal);

         int leftSize = index - inLeft;

         root.left = method(preorder,preLeft+ 1 ,leftSize+preLeft,inorder,inLeft,index- 1 );

         root.right = method(preorder,leftSize+preLeft+ 1 ,preEnd,inorder,index+ 1 ,inEnd);

         return root;

     }

}

/**

  * 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 [] inorder, int [] postorder) {

         return build(inorder, 0 ,inorder.length- 1 ,postorder, 0 ,postorder.length- 1 );

     }

     TreeNode build( int [] inorder, int inStart, int inEnd, int [] postorder, int postStart, int postEnd) {

     if (inStart > inEnd) {

         return null ;

     }

     // root 节点对应的值就是后序遍历数组的最后一个元素

     int rootVal = postorder[postEnd];

     // rootVal 在中序遍历数组中的索引

     int index = 0 ;

     for ( int i = inStart; i <= inEnd; i++) {

         if (inorder[i] == rootVal) {

             index = i;

             break ;

         }

     }

     // 左子树的节点个数

     int leftSize = index - inStart;

     TreeNode root = new TreeNode(rootVal);

     // 递归构造左右子树

     root.left = build(inorder, inStart, index - 1 ,postorder, postStart, postStart + leftSize - 1 );

     root.right = build(inorder, index + 1 , inEnd,postorder, postStart + leftSize, postEnd - 1 );

     return root;

}

}

/**

  * 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 constructFromPrePost( int [] preorder, int [] postorder) {

         return method(preorder, 0 ,preorder.length- 1 ,postorder, 0 ,postorder.length- 1 );

     }

     public TreeNode method( int [] preorder, int preStart, int preEnd, int [] postorder, int postStart, int postEnd){

         if (preStart>preEnd){

             return null ;

         }

         if (preStart==preEnd){

             return new TreeNode(preorder[preStart]);

         }

         int rootVal = preorder[preStart];

         int leftRootVal = preorder[preStart + 1 ];

         int index = 0 ;

         for ( int i = postStart; i < postEnd; i++) {

             if (postorder[i] == leftRootVal) {

                 index = i;

                 break ;

             }

         }

         TreeNode root = new TreeNode(rootVal);

         int leftSize = index - postStart + 1 ;

         root.left = method(preorder, preStart + 1 , preStart + leftSize,postorder, postStart, index);

         root.right = method(preorder, preStart + leftSize + 1 , preEnd,postorder, index + 1 , postEnd - 1 );

         return root;

     }

}