宿州市美丽乡村建设网站,平面设计公司理念,广州珠吉网站建设,南昌企业网站建设哪家好相关推荐 python coding with ChatGPT 打卡第12天| 二叉树#xff1a;理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 python coding with ChatGPT 打卡第15天| 二叉树#xff1a;翻转…相关推荐 python coding with ChatGPT 打卡第12天| 二叉树理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 python coding with ChatGPT 打卡第15天| 二叉树翻转二叉树、对称二叉树 python coding with ChatGPT 打卡第16天| 二叉树完全二叉树、平衡二叉树、二叉树的所有路径、左叶子之和 python coding with ChatGPT 打卡第17天| 二叉树找树左下角的值、路径总和 文章目录 从中序与后序遍历序列构造二叉树Key Points相关题目视频讲解重点分析拓展 最大二叉树Key Points相关题目视频讲解重点分析 从中序与后序遍历序列构造二叉树
Key Points
以 后序数组的最后一个元素为切割点先切中序数组根据中序数组反过来再切后序数组。一层一层切下去每次后序数组最后一个元素就是节点元素。
相关题目
106. 从中序与后序遍历序列构造二叉树 105. 从前序与中序遍历序列构造二叉树
视频讲解
来看看你掉到几次坑
重点分析 if not postorder:return Noneroot TreeNode(postorder[-1])in_root_index inorder.index(root.val)in_left inorder[:in_root_index]in_right inorder[(in_root_index1):]post_left postorder[:len(in_left)]post_right postorder[len(in_left):-1]root.left buildTree(in_left, post_left)root.right buildTree(in_right, post_right)return rootdef buildTree(preorder, inorder):if not preorder:return None# 创建根节点root TreeNode(preorder[0])# 在中序遍历中找到根节点的索引分割中序遍历in_root_index inorder.index(root.val)in_left inorder[:in_root_index]in_right inorder[in_root_index1:]# 分割先序遍历pre_left preorder[1:1len(in_left)]pre_right preorder[1len(in_left):] # 递归构建左右子树root.left buildTree(pre_left, in_left)root.right buildTree(pre_right, in_right)return root 拓展
前序和中序可以唯一确定一棵二叉树。 后序和中序可以唯一确定一棵二叉树。 那么前序和后序可不可以唯一确定一棵二叉树呢 最大二叉树
Key Points
递归调用如下所示
[3,2,1,6,0,5] 中的最大值是 6 左边部分是 [3,2,1] 右边部分是 [0,5] 。 [3,2,1] 中的最大值是 3 左边部分是 [] 右边部分是 [2,1] 。 空数组无子节点。[2,1] 中的最大值是 2 左边部分是 [] 右边部分是 [1] 。 空数组无子节点。只有一个元素所以子节点是一个值为 1 的节点。 [0,5] 中的最大值是 5 左边部分是 [0] 右边部分是 [] 。 只有一个元素所以子节点是一个值为 0 的节点。空数组无子节点。
相关题目
654. 最大二叉树
视频讲解
又是构造二叉树
重点分析
def constructMaximumBinaryTree(nums):if not nums:return Noneroot_val max(nums)root TreeNode(root_val)root_index nums.index(root_val)left nums[:root_index]right nums[root_index1:]root.left constructMaximumBinaryTree(left)root.right constructMaximumBinaryTree(right)return root
