889. Construct Binary Tree from Preorder and Postorder Trave

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

导读：Return any binary tree that matches the given preorder and postorder traversals. Values in the traversals? pre ?and? post ?are distinct?positive integers. ? Example 1: Input: pre = [1,2,4,5,3,6,7],post = [4,7,1] Output: [1,7] ? Note: 1 = p

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals?pre?and?post?are distinct?positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7],post = [4,7,1] Output: [1,7]

Note:

1 <= pre.length == post.length <= 30
pre[]?and?post[]?are both permutations of?1,...,pre.length.
It is guaranteed an answer exists. If there exists multiple answers,you can return any of them.

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 constructFromPrePost(int[] pre,int[] post) {
        return buildTree(pre,pre.length - 1,post,post.length - 1);
    }
    
    public TreeNode buildTree(int[] pre,int pre_start,int pre_end,int[] post,int post_start,int post_end) {
        if(pre_start > pre_end || post_start > post_end) {
            return null;
        }
        
        TreeNode root = new TreeNode(pre[pre_start]);
        if(pre_start + 1 > pre_end) {
            return root;
        }
        
        int idx = 0;
        for(int i = post_start; i <= post_end; i++) {
            if(post[i] == pre[pre_start + 1]) {
                idx = i;
                break;
            }
        }
        
        root.left = buildTree(pre,pre_start + 1,pre_start + idx - post_start + 1,post_start,idx);
        root.right = buildTree(pre,pre_start + idx - post_start + 2,pre_end,idx + 1,post_end - 1);
        
        return root;
    }
}

（编辑：李大同）

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