网页建站费用,百度竞价网站谁做,手机网站建设推荐,企业网站营销的实现方式解读这一部分主要来梳理二叉树题目最简单最基础的部分#xff0c;包括遍历#xff0c;一些简单题目。
一、Leecode 144 - 二叉树的前序遍历
https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
二叉树的遍历是入门。我们需要在程序一开始就创建一个空…这一部分主要来梳理二叉树题目最简单最基础的部分包括遍历一些简单题目。
一、Leecode 144 - 二叉树的前序遍历
https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
二叉树的遍历是入门。我们需要在程序一开始就创建一个空的数组然后递归遍历左右节点将节点放进这个数组内。下面直接给出代码 func preorderTraversal(root *TreeNode) []int {if root nil{return nil}res : make([]int,0)res append(res,root.Val)res append(res,preorderTraversal(root.Left)...)res append(res,preorderTraversal(root.Right)...)return res}
append方法后面的“...”说明 使用append函数和...操作符将这个切片中的所有元素添加到res中。...操作符的作用是将一个切片的所有元素作为独立的参数传递给函数而不是将整个切片作为一个单独的参数。这意味着如果preorderTraversal(root.Left)返回一个切片[a, b, c]append(res, preorderTraversal(root.Left)...)实际上是append(res, a, b, c)。 二、Leecode 94 - 二叉树的中序遍历
https://leetcode.cn/problems/binary-tree-inorder-traversal/
和前序遍历不同但也很类似只是将append的操作放到了递归遍历左右子树的操作中间。
func inorderTraversal(root *TreeNode) []int {if root nil{return nil}res : make([]int,0)res append(res,inorderTraversal(root.Left)...)res append(res,root.Val)res append(res,inorderTraversal(root.Right)...)return res} 三、Leecode 145 - 二叉树的后序遍历
https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
func postorderTraversal(root *TreeNode) []int {res : make([]int,0)if root nil{return nil}res append(res,postorderTraversal(root.Left)...)res append(res,postorderTraversal(root.Right)...)res append(res,root.Val)return res}
四、Leecode 100 - 相同的树
https://leetcode.cn/problems/same-tree/description/
一共有两棵二叉树我们怎么判断他们是一样的要是两棵树都是空的那就是一样的要是有一棵树是空的另一棵树却不是那就不是一样的如果两棵树都不为空但是对应节点的值不一样那也不是一样的。然后我们递归遍历两棵树的左右子树就可以了。
func isSameTree(p *TreeNode, q *TreeNode) bool {if q nil p nil{return true}if q nil || p nil{return false}if p.Val ! q.Val{return false}return isSameTree(p.Left,q.Left) isSameTree(p.Right,q.Right)}
五、Leecode 101 - 对称二叉树
https://leetcode.cn/problems/symmetric-tree/description/
和上面一题的思路一样。不过我们要再写一个辅助函数。来将一个二叉树的左右节点传进去检测左子树的左侧与右子树的右侧以及左子树的右侧与右子树的左侧是否相等。
func isSymmetric(root *TreeNode) bool {// 如果树为空那么它是对称的。if root nil {return true}// 开始从根节点的左右子树进行比较return isMirror(root.Left, root.Right)
}// 辅助函数用于递归比较两个节点是否是镜像对称的
func isMirror(left, right *TreeNode) bool {// 如果两个节点都为空那么它们是对称的if left nil right nil {return true}// 如果其中一个节点为空另一个不为空那么它们不对称if left nil || right nil {return false}// 检查当前两个节点的值是否相等且左节点的左子树和右节点的右子树是否对称// 左节点的右子树和右节点的左子树是否对称return left.Val right.Val isMirror(left.Left, right.Right) isMirror(left.Right, right.Left)
}
六、Leecode 404 - 左叶子之和
https://leetcode.cn/problems/sum-of-left-leaves/
我们需要判断哪些节点是左叶子。然后直接递归。
func sumOfLeftLeaves(root *TreeNode) int {if root nil {return 0}sum : 0// 检查左节点是否为叶节点if root.Left ! nil root.Left.Left nil root.Left.Right nil {sum root.Left.Val}// 递归地累加左右子树的左叶节点的和sum sumOfLeftLeaves(root.Left)sum sumOfLeftLeaves(root.Right)return sum
} 七、Leecode LCP 44 - 开幕式焰火
https://leetcode.cn/problems/sZ59z6/description/
这里我们创建一个set将节点的值放进这个set中遍历完之后直接返回set的长度。在Golang中没有set这个结构所以我们用字典来模拟一样。
func numColor(root *TreeNode) int {set : make(map[int]bool)treeset(root,set)return len(set)}
func treeset(root *TreeNode,set map[int]bool){if root nil{return}set[root.Val] truetreeset(root.Left,set)treeset(root.Right,set)}
