树相关

[hankviv]

[hankviv]

二叉树（Binary Tree） 二叉树是每个节点最多有两个子节点的树。

[hankviv]

二叉搜索树（Binary Search Tree） 二叉查找树又叫二叉搜索树， 左边的所有节点值均小于他根节点的值。 右边的所有节点值均大于他根节点的值。 它的左、右子树也分别为二叉搜索树。

[hankviv]

平衡二叉树（AVL Tree） 定义： 所有节点的左右子树的高度差小于1的二叉树。

[hankviv]

B树（B tree）和 b+树 引用：https://segmentfault.com/a/1190000020416577

[hankviv]

堆： 堆是一种完全二叉树 最大堆和最小堆是二叉堆的两种形式。

最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。

最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。

[hankviv]

三种遍历： 后序遍历： 使用左右中的方式进行遍历。当删除一颗树的所有节点的时候，删除过程将按照后序遍历的顺序进行。 也就是说，当你删除一个节点时，你将首先删除它的左节点和它的右边的节点，然后再删除节点本身。

前序遍历：根左右。 中序遍历：左中右

[hankviv]

递归三种遍历写法：

func preorderTraversal(root *TreeNode)  []int {
    res := []int{}
    if root == nil{
        return res
    }
    res = append(res,root.Val)
    res = append(res,preorderTraversal(root.Left)...)
    res = append(res,preorderTraversal(root.Right)...)
    return res
}

func inorderTraversal(root *TreeNode)  []int {
    res := []int{}
    if root == nil{
        return res
    }
    res = append(res,inorderTraversal(root.Left)...)
    res = append(res,root.Val)
    res = append(res,inorderTraversal(root.Right)...)
    return res
}

func postorderTraversal(root *TreeNode)  []int {
    res := []int{}
    if root == nil{
        return res
    }
    res = append(res,postorderTraversal(root.Left)...)
    res = append(res,postorderTraversal(root.Right)...)
    res = append(res,root.Val)
    return res
}

[hankviv]

先序(preorder)，中序（inorder），后序(postorder)

[hankviv]

二叉树求最大深度： https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/submissions/ 深度优先 DFS写法：

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

广度优先 BFS写法

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{}
    queue = append(queue, root)
    ans := 0
    for len(queue) > 0 {
        sz := len(queue)
        for sz > 0 {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            sz--
        }
        ans++
    }
    return ans
}

[hankviv]

二叉树层序遍历： https://leetcode-cn.com/problems/binary-tree-level-order-traversal

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    queue := []*TreeNode{}
    res := [][]int{}

    queue = append(queue, root)

    for len(queue) > 0 {
        lens := len(queue)

        nodeRes := []int{}
        for lens > 0 {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            nodeRes = append(nodeRes, node.Val)
            lens--
        }
        res = append(res, nodeRes)
    }
    return res
}

[hankviv]

二叉树中序遍历栈写法： 先把左树全部入栈，一直到nil，然后出栈，出栈后看是否有右子树，有就遍历，没有的话继续出栈，如果有有右子树的话 继续把右子树继续遍历。

func inorderTraversal(root *TreeNode) (res []int) {
    stack := []*TreeNode{}
    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, root.Val)
        root = root.Right
    }
    return
}

[hankviv]

二叉树遍历 前序遍历 闭包写法 模版

func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode) {
        if root == nil{
            return
        }
        res = append(res,root.Val)
        dfs(root.Left)
        dfs(root.Right)
    }
    dfs(root)
    return res
}

[hankviv]

迭代遍历 二叉树

前序遍历：

//前序遍历和中序遍历 区别 就是 前序入栈前 存储节点 出栈不存储
func preorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    res := []int{}
    for root != nil || len(stack) > 0 {
        for root != nil {
            res  = append(res,root.Val)
            stack = append(stack,root)
            root = root.Left
        }
        root = stack[len(stack) -1]
        stack = stack[:len(stack) -1]
        root = root.Right
    }
    return res
}

中序遍历：

//中序入栈前不存储 出栈再存储
func inorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    res := []int{}
    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, root.Val)
        root = root.Right
    }
    return res
}

后序遍历

func postorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    res := []int{}
    var prev *TreeNode
    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        //如果节点右树为空的话 说明已经到了根节点 就将此节点存入结果，继续从栈取 （并且标记这个节点上次访问过）
        //如果节点右树不为空，但是标记这个节点右边是上一次访问的节点 表示节点左右树都被访问过了。就将此节点存入结果，继续从栈取 （并且标记这个节点上次访问过）
        //如果右树不为空 且右边节点上次也没访问的话 就访问右边这个树
        if root.Right == nil || root.Right == prev {
            res = append(res, root.Val)
            prev = root
            root = nil
        } else {
            stack = append(stack, root)
            root = root.Right
        }
    }
    return res
}