笔记，感觉 up 主分享。代码都是用 golang 实现。
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}func NewBinaryTree() *TreeNode {
root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 3}
root.Left.Left = &TreeNode{Val: 4}
root.Left.Left.Right = &TreeNode{Val: 5}
root.Right.Left = &TreeNode{Val: 6}
}func PreOrder(root *TreeNode, ans *[]int) {
if root == nil {
return
}
fmt.Println(root.Val)
*ans = append(*ans, root.Val)
PreOrder(root.Left, ans)
PreOrder(root.Right, ans)
}func InOrder(root *TreeNode, ans *[]int) {
if root == nil {
return
}
InOrder(root.Left, ans)
fmt.Println(root.Val)
*ans = append(*ans, root.Val)
InOrder(root.Right, ans)
}func PostOrder(root *TreeNode, ans *[]int) {
if root == nil {
return
}
PostOrder(root.Left, ans)
PostOrder(root.Right, ans)
fmt.Println(root.Val)
*ans = append(*ans, root.Val)
}
| method | average | worst case |
|---|---|---|
| insert | O(logn) | O(n) |
| Search | O(logn) | O(n) |
| Delete | O(logn) | O(n) |
func NewBST(nums []int) *TreeNode {
var root *TreeNode
for _, num := range nums {
root = insert(root, num)
}
return root
}
func insert(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val: val}
}
if val < root.Val {
root.Left = insert(root.Left, val)
} else {
root.Right = insert(root.Right, val)
}
return root
}TODO
培养递归思维，视频中有个例子，查找树节点中值最大的，
普通思路是先设定最小值，然后遍历整棵树，如果大于就修改最大值。
递归思路先获取左子树的最大值，然后获取右子树的最大值，然后和根节点取最大值。
func FindMaxValTree(root *TreeNode) int {
_max := math.MinInt16
traverse(root, &_max)
return _max
}
func traverse(root *TreeNode, _max *int) {
if root == nil {
return
}
*_max = max(root.Val, *_max)
traverse(root.Left, _max)
traverse(root.Right, _max)
}func FindMaxValTree2(root *TreeNode) int {
if root == nil {
return math.MinInt16
}
maxLeft := FindMaxValTree2(root.Left)
maxRight := FindMaxValTree2(root.Right)
bigger := max(maxLeft, maxRight)
return max(bigger, root.Val)
}
func solve(root){
if not root: return ...
if f(root): retunr ...
l = solve(root.left)
r = solve(root.right)
return g(root, l, r)
}func solve(p, q){
if not p and not q{
return ...
}
if f(p, q): return ...
c1 = solve(p.left, q.right)
c2 = solve(p.left, q.right)
return g(p,q,c1,c2)
}