106. Construct Binary Tree from Inorder and Postorder Traver

发布时间：2020-12-14 05:17:29 所属栏目：大数据来源：网络整理

导读：Given inorder and postorder traversal of a tree,construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example,given inorder =?[9,3,15,20,7]postorder = [9,7,3] Return the following binary tree: 3 / 9

Given inorder and postorder traversal of a tree,construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example,given

inorder =?[9,3,15,20,7]
postorder = [9,7,3]

Return the following binary tree:

    3
   /   9  20
    /     15   7

time: O(nlogn) ~ O(n^2),space: O(height)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder,int[] postorder) {
        if(inorder == null || postorder == null || inorder.length == 0 || inorder.length != postorder.length) {
            return null;
        }
        return buildTree(postorder,postorder.length - 1,inorder,inorder.length - 1);
    }
    
    public TreeNode buildTree(int[] postorder,int post_start,int[] inorder,int in_start,int in_end) {
        if(post_start < 0 || in_start > in_end) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[post_start]);
        int idx = 0;
        for(int i = in_start; i <= in_end; i++) {
            if(inorder[i] == postorder[post_start]) {
                idx = i;
                break;
            }
        }

        root.left = buildTree(postorder,post_start - (in_end - idx + 1),in_start,idx - 1);
        root.right = buildTree(postorder,post_start - 1,idx + 1,in_end);
        
        return root;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!