Leetcode: Construct Binary Tree from Preorder and Postorder Traversal

Construct Binary Tree from Preorder and Postorder Traversal



Similar Problems:


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,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/construct-binary-tree-from-preorder-and-postorder-traversal
// Basic Ideas:
// Complexity: Time ?, Space O?
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructFromPrePost(pre []int, post []int) *TreeNode {
    if len(pre) == 0 { return nil }
    res := &TreeNode{pre[0], nil, nil}
    if len(pre) == 1 { return res }
    for i:=len(pre)-1; i>=0; i-- {
        if post[i] == pre[1] {
            res.Left = constructFromPrePost(pre[1:i+2], post[0:i+1])
            res.Right = constructFromPrePost(pre[i+2:], post[i+1:len(pre)-1])
            break
        }
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.