（Golang）leetcode Hot100 第四部分 二叉树

//94.二叉树的中序遍历
func inorderTraversal(root *TreeNode) []int {
var traversal func(node *TreeNode)
res := []int{}
traversal = func(node *TreeNode) {
if node == nil {
return
}
//左中右
traversal(node.Left)
res = append(res, node.Val)
traversal(node.Right)
}
    traversal(root)
    return res
}

//102.二叉树的层序遍历
func levelOrder(root *TreeNode) [][]int {
res := [][]int{}  //二维数组存结果
que := list.New() //定义一个双向链表模拟队列
if root != nil {
que.PushBack(root)
} else {
return nil
}
for que.Len() > 0 {
res_row := []int{} //存放每一层的结果
length := que.Len()
for length > 0 {
            //取出队首元素
node := que.Front().Value.(*TreeNode)
            //将这个元素的左右孩子加入队列
if node.Left != nil {
que.PushBack(node.Left)
}
if node.Right != nil {
que.PushBack(node.Right)
}
            //将这个元素加入这一行的结果集
            row = append(res_row, node.Val)
            //移除这个元素
que.Remove(que.Front())
length--
}
res = append(res, res_row)

}
return res

}

//104.二叉树的右视图
func rightSideView(root *TreeNode) []int {
res := []int{}
que := list.New()
if root != nil {
que.PushBack(root)
} else {
return nil
}
for que.Len() > 0 {
len := que.Len()
for len > 0 {
node := que.Front().Value.(*TreeNode)
if node.Left != nil {
que.PushBack(node.Left)
}
if node.Right != nil {
que.PushBack(node.Right)
}
            //将最右边的元素加入结果集中
            if len==1{
                res=append(res,node.Val)
            }
            //移除队首元素
            que.Remove(que.Front())
            len--
}
}
    return res
}

//104.二叉树的最大深度
func maxDepth(root *TreeNode) int {
res := 0
que := list.New()
if root != nil {
que.PushBack(root)
} else {
return 0
}
for que.Len() > 0 {
res_row := []int{}
len := que.Len()
for len > 0 {
node := que.Front().Value.(*TreeNode)
if node.Left != nil {
que.PushBack(node.Left)
}
if node.Right != nil {
que.PushBack(node.Right)
}
res_row = append(res_row, node.Val)
que.Remove(que.Front())
len--
}
res++
}
return res
}

//226.翻转二叉树
func invertTree(root *TreeNode) *TreeNode {
var invert func(node *TreeNode)
invert = func(node *TreeNode) {
if node == nil {
return
}
//前序遍历
node.Left, node.Right = node.Right, node.Left //交换左右孩子
invert(node.Left)
invert(node.Right)
}
invert(root)
return root
}

//101.对称二叉树
func isSymmetric(root *TreeNode) bool {
var comp func(left *TreeNode, right *TreeNode) bool
comp = func(left *TreeNode, right *TreeNode) bool {
// 终止条件
if left == nil && right != nil {
return false
} else if left != nil && right == nil {
return false
} else if left == nil && right == nil {
return true
} else if left.Val != right.Val { //这里最后判断两值是否相等，避免出现nil
return false
}
//注意这里要用后序遍历，因为要统计该节点的左右孩子信息返回给上一层
inside := comp(left.Right, right.Left)
outside := comp(left.Left, right.Right)
return inside && outside
}
res := comp(root.Left, root.Right)
return res
}

//98.验证二叉搜索树
func isValidBST(root *TreeNode) bool {
// 中序遍历
var ifvalid func(node *TreeNode) bool
var pre *TreeNode //用于记录上一个结点的值
ifvalid = func(node *TreeNode) bool {
if node == nil {
return true
}
left := ifvalid(node.Left)
if pre != nil && pre.Val >= node.Val { //注意这里要有等号
return false
}
pre = node
right := ifvalid(node.Right)
return left && right //左子树右子树都符合条件
}
res := ifvalid(root)
return res
}

//108.将有序数组转换为二叉搜索树
func sortedArrayToBST(nums []int) *TreeNode {
var traversal func(nums []int, left, right int) *TreeNode//left、right存元素下标
traversal = func(nums []int, left, right int) *TreeNode {
//终止条件
if left > right {
return nil
}
mid := (left + right) / 2
root := &TreeNode{Val: nums[mid]}//注意：构造根结点的方法！！！
root.Left = traversal(nums, left, mid-1)
root.Right = traversal(nums, mid+1, right)
return root
}
root := traversal(nums, 0, len(nums)-1)
return root

}

原文地址：https://blog.csdn.net/fdyw_gzl/article/details/136983706

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！