从前序遍历与中序遍历序列构造二叉树、从中序遍历与后序遍历序列构造二叉树、有序数组转换成二叉搜索树、有序链表转换成二叉搜索树、二叉树展开为链表

树与其他数据结构转换

1.1.从前序与中序遍历序列构造二叉树 (opens new window)

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

hon输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

笔记

对于任意一颗树而言，前序遍历的形式总是:

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是:

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

确定根节点后，递归建立左右子树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
      """
      对于任意一颗树而言，前序遍历的形式总是

      [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
      即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

      [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

      """
      
      if len(preorder) == 0:
          return None
      
      val = preorder[0]
      root = TreeNode(val=val)
      index = 0
      for index, j in enumerate(inorder):
          if val == j:
              break
      root.left = self.buildTree(preorder[1:index+1], inorder[:index])
      root.right = self.buildTree(preorder[index+1:], inorder[index+1:])

      return root

/**
* 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) == 0{
      return nil
  }

  root := &TreeNode{Val: preorder[0]}
  index := 0
  for index_, val := range inorder{
      if val == root.Val{
          index = index_
          break
      }
  }
  root.Left = buildTree(preorder[1: index+1], inorder[:index])
  root.Right = buildTree(preorder[index+1:], inorder[index+1:])
  return root

}

// Make sure to add code blocks to your code group

1.2.从中序与后序遍历序列构造二叉树 (opens new window)

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  # 二叉树中序遍历的顺序是根节点的左节点的中序遍历 根节点  根节点的有子树的中序遍历结果
  #[[左子树的中序遍历], 根, [右子树的中序遍历]]
  # 二叉树的后序遍历顺序是根节点左子树的后序遍历 根节点的右子树的后序遍历 根节点
  #[[左子树的后序遍历],[右子树的后序遍历], 根]
  def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
      if len(inorder) == 0:
          return None
      
      root = TreeNode(val=postorder[len(postorder)-1])
      index = 0
      while inorder[index] != root.val:
          index += 1
      
      root.left = self.buildTree(inorder[:index], postorder[:index])
      root.right = self.buildTree(inorder[index+1:], postorder[index:len(postorder)-1])
      return root
      

/**
* 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) == 0{
      return nil
  }

  root := &TreeNode{Val: postorder[len(postorder)-1]}

  index := 0
  for inorder[index] != root.Val{
      index ++
  }
  root.Left = buildTree(inorder[:index], postorder[:index])
  root.Right = buildTree(inorder[index+1:], postorder[index:len(postorder)-1])
  return root
}

// Make sure to add code blocks to your code group

1.3.将有序数组转换为二叉搜索树 (opens new window)

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵

平衡

二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:

      def dfs(start, end):
          if start > end:
              return None
          
          curNode = (start + end)// 2
          root = TreeNode(nums[curNode])
          root.left = dfs(start, curNode-1)
          root.right = dfs(curNode+1,end)
          return root
      return dfs(0, len(nums)-1)
      

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func sortedArrayToBST(nums []int) *TreeNode {
  // 平衡二叉搜索树
  
  var dfs func(start, end int) *TreeNode

  dfs = func(start, end int) *TreeNode{
      if start>end{
          return nil
      }
      mid := (start+end)/2

      root := &TreeNode{Val:nums[mid]}
      root.Left = dfs(start, mid - 1)
      root.Right = dfs(mid + 1, end)
      return root
  }
  
  return dfs(0, len(nums)-1)
}

// Make sure to add code blocks to your code group

1.4.有序链表转换二叉搜索树 (opens new window)

给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为

平衡

二叉搜索树。

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []
输出: []

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
      
      def buildTress(left, right):
          if left >right:
              return None
          mid = (left+right)//2
          node = TreeNode(nums[mid].val)
          node.left = buildTress(left, mid-1)
          node.right = buildTress(mid+1, right)
          return node

      nums = []
      while head:
          nums.append(head)
          head = head.next
      return buildTress(0, len(nums)-1)

/**
* Definition for singly-linked list.
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func sortedListToBST(head *ListNode) *TreeNode {
  ret := buildTree(head, nil)
  return ret

}

func getMiddleNode(left, right *ListNode) *ListNode{
  fast := left
  slow := left
  for fast != right && fast.Next != right{
      fast = fast.Next.Next
      slow = slow.Next
  }
  return slow
}

func buildTree(left, right *ListNode) *TreeNode{
  if left ==right{
      return nil
  }
  mid := getMiddleNode(left, right)
  curnode := &TreeNode{Val:mid.Val}
  curnode.Left = buildTree(left, mid)
  curnode.Right = buildTree(mid.Next, right)
  return curnode
}

// Make sure to add code blocks to your code group

1.5.二叉树展开为链表 (opens new window)

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 (opens new window) 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def flatten(self, root: Optional[TreeNode]) -> None:
      """
      Do not return anything, modify root in-place instead.
      """
      stack, cur = list(), root
      ret = list()
      while stack or cur:
          while cur:
              stack.append(cur)
              ret.append(cur)
              cur = cur.left
          cur = stack.pop()
          cur = cur.right
      for i in range(1, len(ret)):
          prev, cur = ret[i-1], ret[i]
          prev.left = None
          prev.right = cur

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func flatten(root *TreeNode)  {

  ret, stack := make([]*TreeNode, 0), make([]*TreeNode, 0)

  for root != nil || len(stack)>0{

      for root != nil{
          ret = append(ret, root)
          stack = append(stack, root)
          root = root.Left
      }
      cur := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      root = cur.Right
  }
  // ret是先序遍历的结果
  for i:=0;i<len(ret)-1;i++{
      cur := ret[i]
      nxt := ret[i+1]
      cur.Right = nxt
      cur.Left =nil

  }

}

// Make sure to add code blocks to your code group

1.6填充每个节点的下一个右侧节点指针 (opens new window)

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

输入：root = []
输出：[]

"""
# Definition for a Node.
class Node:
  def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
      self.val = val
      self.left = left
      self.right = right
      self.next = next
"""

class Solution:
  def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
      if not root:
          return root
      queue = collections.deque([root])

      ret = list()
      while queue:
          size = len(queue)
          for i in range(size):
              cur = queue.popleft()
              if i != size-1:
                  cur.next = queue[0]
              else:
                  cur.next = None
              if cur.left:
                  queue.append(cur.left)
              if cur.right:
                  queue.append(cur.right)
      return root
              
      

// Make sure to add code blocks to your code group