LeetCode 树

发表信息: August 26, 2019 by gc

文章分类:
LeetCode 6

94 二叉树的中序遍历
95 不同的二叉搜索树II
96 不同的二叉搜索树
98 验证二叉搜索树
100 相同的树
99 恢复二叉树
101 对称二叉树
102. 二叉树的层次遍历
103 二叉树的矩形遍历
104 二叉树的最大深度
110 平衡二叉树

94 二叉树的中序遍历

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	result := make([]int, 0)
	if root == nil {
		return result
	}

	result = append(result, inorderTraversal(root.Left)...)
	result = append(result, (*root).Val)
	result = append(result, inorderTraversal(root.Right)...)

	return result
}

95 不同的二叉搜索树II

func generateTreesMore(points []int) []*TreeNode {
	result := make([]*TreeNode, 0)
	if len(points) == 1 {
		result = append(result, &TreeNode{points[0], nil, nil})
		return result
	}

	if len(points) == 0 {
		return result
	}

	for i, _ := range points {
		leftTrees := generateTreesMore(points[:i])
		rightTrees := generateTreesMore(points[i+1:])

		if len(leftTrees) == 0 {
			for _, v := range rightTrees {
				result = append(result, &TreeNode{points[i], nil, v})
			}
		} else if len(rightTrees) == 0 {
			for _, v := range leftTrees {
				result = append(result, &TreeNode{points[i], v, nil})
			}
		} else {
			for _, l := range leftTrees {
				for _, r := range rightTrees {
					result = append(result, &TreeNode{points[i], l, r})
				}
			}
		}
	}

	return result
}

func generateTrees(n int) []*TreeNode {
	points := make([]int, 0)
	for i := 1; i <= n; i++ {
		points = append(points, i)
	}

	return generateTreesMore(points)
}

自己A的，牛逼的不得了

96 不同的二叉搜索树

func generateTreesMoreNum(points []int) int {
	if len(points) == 1 {
		return 1
	}

	if len(points) == 0 {
		return 0
	}

	result := 0
	for i, _ := range points {
		leftResult := generateTreesMoreNum(points[:i])
		rightResult := generateTreesMoreNum(points[i+1:])

		if leftResult == 0 {
			result += rightResult
		} else if rightResult == 0 {
			result += leftResult
		} else {
			result += leftResult * rightResult
		}
	}

	return result
}

func numTrees(n int) int {
	points := make([]int, 0)
	for i := 1; i <= n; i++ {
		points = append(points, i)
	}

	return generateTreesMoreNum(points)
}

98 验证二叉搜索树

func midShow(root *TreeNode) []int {
	if root == nil {
		return make([]int, 0)
	}

	result := make([]int, 0)
	result = append(result, midShow(root.Left)...)
	result = append(result, root.Val)
	result = append(result, midShow(root.Right)...)

	return result
}

func isValidBST(root *TreeNode) bool {
	l := midShow(root)
	if len(l) == 0 {
		return true
	}

	min := l[0]
	for _, v := range l[1:] {
		if v <= min {
			return false
		}
		min = v
	}

	return true
}

100 相同的树

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}

	if p == nil && q != nil {
		return false
	}

	if q == nil && p != nil {
		return false
	}

	if q.Val != p.Val {
		return false
	}

	return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

99 恢复二叉树

func midShowForNode(root *TreeNode) ([]*TreeNode, []int) {
	nodeResult := make([]*TreeNode, 0)
	intResult := make([]int, 0)

	if root.Left == nil && root.Right == nil {
		nodeResult = append(nodeResult, root)
		intResult = append(intResult, root.Val)
		return nodeResult, intResult
	}

	if root.Left != nil {
		a, b := midShowForNode(root.Left)
		nodeResult = append(nodeResult, a...)
		intResult = append(intResult, b...)
	}

	nodeResult = append(nodeResult, root)
	intResult = append(intResult, root.Val)

	if root.Right != nil {
		a, b := midShowForNode(root.Right)
		nodeResult = append(nodeResult, a...)
		intResult = append(intResult, b...)
	}

	return nodeResult, intResult
}

func recoverTree(root *TreeNode) {
	midShowList, midIntList := midShowForNode(root)
	sort.Ints(midIntList)
	errorAI := -1
	errorBI := -1
	for i, _ := range midIntList {
		if midShowList[i].Val != midIntList[i] {
			if errorAI == -1 {
				errorAI = i
			} else {
				errorBI = i
			}
		}
	}

	midShowList[errorAI].Val, midShowList[errorBI].Val = midShowList[errorBI].Val, midShowList[errorAI].Val
}

这里有个空间复杂度是常数的

func midShowForNode(root *TreeNode) []*TreeNode {
	nodeResult := make([]*TreeNode, 0)
	if root.Left == nil && root.Right == nil {
		nodeResult = append(nodeResult, root)
		return nodeResult
	}

	if root.Left != nil {
		a := midShowForNode(root.Left)
		nodeResult = append(nodeResult, a...)
	}

	nodeResult = append(nodeResult, root)

	if root.Right != nil {
		a := midShowForNode(root.Right)
		nodeResult = append(nodeResult, a...)
	}

	return nodeResult
}

func recoverTree(root *TreeNode) {
	midShowList := midShowForNode(root)
	var errorNode1 *TreeNode = nil
	var errorNode2 *TreeNode = nil
	for i, _ := range midShowList {
		if i == 0 {
			continue
		}
		if errorNode1 == nil && midShowList[i-1].Val > midShowList[i].Val {
			errorNode1 = midShowList[i-1]
		}

		if errorNode1 != nil && midShowList[i-1].Val > midShowList[i].Val {
			errorNode2 = midShowList[i]
		}
	}

	errorNode1.Val, errorNode2.Val = errorNode2.Val, errorNode1.Val
}

101 对称二叉树

func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}

	return isImageTree(root.Left, root.Right)
}

func isImageTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if q == nil || p == nil {
		return false
	}

	return q.Val == p.Val && isImageTree(p.Left, q.Right) && isImageTree(q.Left, p.Right)
}

这么简单的问题，递归左和右一致就行

102. 二叉树的层次遍历

func levelOrder(root *TreeNode) [][]int {
	result := make([][]int, 0)
	allNode := make([]*TreeNode, 0)

	if root == nil {
		return result
	} else {
		// 初始化第一个root
		group := make([]int, 0)
		group = append(group, root.Val)
		if root.Left != nil {
			allNode = append(allNode, root.Left)
		}
		if root.Right != nil {
			allNode = append(allNode, root.Right)
		}
		result = append(result, group)
	}
	for ; len(allNode) > 0; {
		group := make([]int, 0)
		allNodeTemp := make([]*TreeNode, 0)
		for _, v := range allNode {
			group = append(group, v.Val)
			if v.Left != nil {
				allNodeTemp = append(allNodeTemp, v.Left)
			}
			if v.Right != nil {
				allNodeTemp = append(allNodeTemp, v.Right)
			}
		}

		result = append(result, group)
		allNode = allNodeTemp
	}

	return result
}

103 二叉树的矩形遍历

func zigzagLevelOrder(root *TreeNode) [][]int {
	result := make([][]int, 0)
	if root == nil {
		return result
	}

	stack := list.New()
	stack.PushBack(root)

	forwad := true
	for ; stack.Len() > 0; {
		childs := make([]*TreeNode, 0)
		group := make([]int, 0)
		for ; stack.Len() > 0; {
			back := stack.Back()
			stack.Remove(back)
			oneNode := back.Value.(*TreeNode)
			group = append(group, oneNode.Val)

			if forwad {
				if oneNode.Left != nil {
					childs = append(childs, oneNode.Left)
				}
				if oneNode.Right != nil {
					childs = append(childs, oneNode.Right)
				}
			} else {
				if oneNode.Right != nil {
					childs = append(childs, oneNode.Right)
				}
				if oneNode.Left != nil {
					childs = append(childs, oneNode.Left)
				}
			}
		}
		forwad = !forwad
		result = append(result, group)
		for _, v := range childs {
			stack.PushBack(v)
		}
	}
	return result
}

这里有个点特别注意在golang中强制类型转换back.Value.(*TreeNode)

104 二叉树的最大深度

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	if root.Left == nil && root.Right == nil {
		return 1
	}

	leftMaxDepth := maxDepth(root.Left)
	rightMaxDepth := maxDepth(root.Right)

	return int(1 + math.Max(float64(leftMaxDepth), float64(rightMaxDepth)))
}

110 平衡二叉树

func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}

	maxLeftDepth := MaxDepth(root.Left)
	maxRightDepth := MaxDepth(root.Right)

	return math.Abs(float64(maxLeftDepth)-float64(maxRightDepth)) <= 1.0 && isBalanced(root.Left) && isBalanced(root.Right)
}

func MaxDepth(tree *TreeNode) int {
	if tree == nil {
		return 0
	}
	if tree.Left == nil && tree.Right == nil {
		return 1
	}

	leftMaxDepth := MaxDepth(tree.Left)
	rightMaxDepth := MaxDepth(tree.Right)

	return int(1 + math.Max(float64(leftMaxDepth), float64(rightMaxDepth)))
}