golang刷leetcode 前序＋中序／中序＋后序构造二叉树

golangLeetcode

发布于 2022-08-02 15:50:55

2620

发布于 2022-08-02 15:50:55

文章被收录于专栏：golang算法架构leetcode技术php

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

解题思路：

1，前序遍历的话第一个一定是根

2，中序遍历的话和根元素相等的元素左边一定在左子树，设根元素位置为i

3，前序遍历，前长度为i+1的元素一定在左子树

4，递归求解

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
  if len(preorder) < 1 || len(inorder) < 1 {
    return nil
  }
  if len(preorder) == 1 {
    return &TreeNode{
      Val: preorder[0],
    }
  }
  if len(inorder) == 1 {
    return &TreeNode{
      Val: inorder[0],
    }
  }

  i := 0
  for ; i < len(inorder); i++ {
    if preorder[0] == inorder[i] {
      break
    }
  }
  if i == len(inorder) {
    return nil
  }
  h := &TreeNode{
    Val: preorder[0],
  }

  if i == 0 {
    h.Right = buildTree(preorder[1:], inorder[i+1:])
  } else if i == len(inorder)-1 {
    h.Left = buildTree(preorder[1:], inorder[:i])
  } else {
    h.Left = buildTree(preorder[1:i+1], inorder[:i])
    h.Right = buildTree(preorder[i+1:], inorder[i+1:])
  }
  return h
}

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

解题思路：

1，后序遍历的话最后一个一定是根

2，中序遍历的话和根元素相等的元素左边一定在左子树，设根元素位置为i

3，后序遍历，前长度为i+1的元素一定在左子树

4，递归求解

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
    if len(inorder)<1 ||len(postorder)<1{
        return nil
    }
    if len(inorder)==1{
        return &TreeNode{Val:inorder[0]}
    }
    i:=0
    for ;i<len(inorder);i++{
        if postorder[len(postorder)-1]==inorder[i]{
            break
        }
    }
    h:=&TreeNode{Val:postorder[len(postorder)-1]}
    if i==len(postorder)-1{
        h.Left=buildTree(inorder[:i],postorder[:i])
    }else if i==0{
        h.Right=buildTree(inorder[1:],postorder[:len(postorder)-1])
    }else{
        h.Left=buildTree(inorder[:i],postorder[:i])
         h.Right=buildTree(inorder[i+1:],postorder[i:len(postorder)-1])
    }
    return h
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-03-12，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树