网站ftp查询,爬虫代理ip购买,深圳设计外包服务,做pos机网站有必要么leeocode地址#xff1a;从中序与后序遍历序列构造二叉树 给定两个整数数组 inorder 和 postorder #xff0c;其中 inorder 是二叉树的中序遍历#xff0c; postorder 是同一棵树的后序遍历#xff0c;请你构造并返回这颗 二叉树 。
示例 1:
输入#xff1a;inorder …leeocode地址从中序与后序遍历序列构造二叉树 给定两个整数数组 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]
提示: 1 inorder.length 3000 postorder.length inorder.length -3000 inorder[i], postorder[i] 3000 inorder 和 postorder 都由 不同 的值组成 postorder 中每一个值都在 inorder 中 inorder 保证是树的中序遍历 postorder 保证是树的后序遍历
实现思路
中序遍历Inorder左子树 - 根节点 - 右子树 后序遍历Postorder左子树 - 右子树 - 根节点 通过给定的中序遍历和后序遍历数组我们可以确定二叉树的根节点以及左右子树的范围。具体步骤如下 步骤1后序遍历的最后一个元素是根节点的值。 步骤2在中序遍历中找到根节点的位置其左侧为左子树的中序遍历右侧为右子树的中序遍历。 步骤3根据步骤2中左右子树的大小可以在后序遍历中确定左子树和右子树的后序遍历。 递归地应用以上步骤即可构造整棵二叉树。
代码实现
# Definition for a binary tree node.
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef buildTree(inorder, postorder):if not inorder or not postorder:return Noneroot_val postorder.pop()root TreeNode(root_val)idx inorder.index(root_val)root.right buildTree(inorder[idx 1:], postorder)root.left buildTree(inorder[:idx], postorder)return rootdef inorderTraversal(root):if not root:return []return inorderTraversal(root.left) [root.val] inorderTraversal(root.right)# Example
inorder [9, 3, 15, 20, 7]
postorder [9, 15, 7, 20, 3]root buildTree(inorder, postorder)# Verify the constructed tree by printing its inorder traversal
print(Inorder traversal of constructed tree:, inorderTraversal(root))
go实现
package mainimport fmttype TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func buildTree(inorder []int, postorder []int) *TreeNode {if len(inorder) 0 || len(postorder) 0 {return nil}rootVal : postorder[len(postorder)-1]root : TreeNode{Val: rootVal}idx : indexOf(inorder, rootVal)root.Left buildTree(inorder[:idx], postorder[:idx])root.Right buildTree(inorder[idx1:], postorder[idx:len(postorder)-1])return root
}func indexOf(arr []int, val int) int {for i : range arr {if arr[i] val {return i}}return -1
}func inorderTraversal(root *TreeNode) []int {var result []intvar inorder func(node *TreeNode)inorder func(node *TreeNode) {if node nil {return}inorder(node.Left)result append(result, node.Val)inorder(node.Right)}inorder(root)return result
}func main() {// Exampleinorder : []int{9, 3, 15, 20, 7}postorder : []int{9, 15, 7, 20, 3}root : buildTree(inorder, postorder)// Verify the constructed tree by printing its inorder traversalfmt.Println(Inorder traversal of constructed tree:, inorderTraversal(root))
}
kotlin实现
class TreeNode(var val: Int) {var left: TreeNode? nullvar right: TreeNode? null
}fun buildTree(inorder: IntArray, postorder: IntArray): TreeNode? {if (inorder.isEmpty() || postorder.isEmpty()) {return null}val rootVal postorder.last()val root TreeNode(rootVal)val idx inorder.indexOf(rootVal)root.left buildTree(inorder.sliceArray(0 until idx), postorder.sliceArray(0 until idx))root.right buildTree(inorder.sliceArray(idx 1 until inorder.size), postorder.sliceArray(idx until postorder.size - 1))return root
}fun inorderTraversal(root: TreeNode?): ListInt {val result mutableListOfInt()fun inorder(node: TreeNode?) {if (node null) returninorder(node.left)result.add(node.val)inorder(node.right)}inorder(root)return result
}fun main() {// Exampleval inorder intArrayOf(9, 3, 15, 20, 7)val postorder intArrayOf(9, 15, 7, 20, 3)val root buildTree(inorder, postorder)// Verify the constructed tree by printing its inorder traversalprintln(Inorder traversal of constructed tree: ${inorderTraversal(root)})
}
