网站建设的所有权,网站怎么ftp,拓者设计吧网站,为网站 做字幕前言
今天是构建二叉树和处理两个二叉树的问题。重点#xff1a;单调栈的思想#xff0c;后续模块会专门刷题。
内容
一、最大二叉树
654. 最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点#xff0c;其…前言
今天是构建二叉树和处理两个二叉树的问题。重点单调栈的思想后续模块会专门刷题。
内容
一、最大二叉树
654. 最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
递归
func constructMaximumBinaryTree(nums []int) *TreeNode {if len(nums)0{return nil}index:findMax(nums)root:TreeNode{Val:nums[index],Left:constructMaximumBinaryTree(nums[:index]),Right:constructMaximumBinaryTree(nums[index1:]),}//三个逗号return root
}func findMax(nums []int)int{index:0for i,v:range nums{if nums[index]v{indexi}}return index
}
单调栈
在解决类似于“下一个更大元素”的问题时非常好用
单调栈中存放的数据应该是有序的所以单调栈也分为单调递增栈和单调递减栈 单调递增栈单调递增栈就是从栈底到栈顶数据是从大到小
单调递减栈单调递减栈就是从栈底到栈顶数据是从小到大 维持一个单调递增的栈
当节点值大于栈顶时弹出栈顶作为当前节点的左孩子
栈顶的右孩子就是当前节点
当前节点加入栈
func constructMaximumBinaryTree(nums []int)*TreeNode{stack:[]*TreeNode{}for _,num:range nums{cur:TreeNode{num,nil,nil}for len(stack)0stack[len(stack)-1].Valnum{cur.Leftstack[len(stack)-1]stackstack[:len(stack)-1]}if len(stack)0{stack[len(stack)-1].Rightcur}stackappend(stack,cur)}return stack[0]
}
//同一个节点的左右子树会被多次赋值
二、合并二叉树
617. 合并二叉树
给你两棵二叉树 root1 和 root2 。
想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
深度优先搜索
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {if root1nil{return root2}if root2nil{return root1}//修改root1 or 新建一个树// root1.Valroot2.Val// root1.LeftmergeTrees(root1.Left,root2.Left)// root1.RightmergeTrees(root1.Right,root2.Right)// return root1 root:TreeNode{Val:root1.Valroot2.Val,Left:mergeTrees(root1.Left,root2.Left),Right:mergeTrees(root1.Right,root2.Right),}return root
}
最后
坚持
