Leetcode With Golang 二叉树 part1

这一部分主要来梳理二叉树题目最简单最基础的部分，包括遍历，一些简单题目。

一、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)}