Posted at 2021-03-14Updated at 2021-03-25 算法算法数据结构

树是常用的数据结构，应用较多的有二叉搜索树，二叉平衡搜索树(AVL树)，红黑树，多路平衡搜索树(B-树，B+树，B*树)等。

# 基础

树可由链式结构或数组实现，遍历方式为前、中、后、层序遍历。

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

# 树

有向无环非线性数据结构，每个节点可以指向多个节点，但至多有一个节点指向自身。

# 二叉树

每个节点至多只能指向两个节点。

# 满二叉树

只有度为0和2的节点，并且度为0的节点在同一层上。

# 完全二叉树

除了最底层节点可能没填满外，其余层节点数均达到最大值，并且最下面一层的节点应集中在最左侧。

# 二叉搜索树

一种朴素的有序树结构，左子节点均小于父节点，右子节点均大于父节点。当插入新值时由根节点开始按以上规则逐层比较，直到找到合适的叶节点位置。

优点：不需要在插入数据时调整结构
缺点：性能易受数据插入顺序影响，最差情况为顺序插入，退化为链表。

# 平衡二叉搜索树(AVL树)

二叉搜索树的改进，又称AVL(Adelson-Velsky and Landis)树，引入平衡因子，通过旋转操作保证所有子树高度差不超过1。

优点：相比二叉树更平衡，极端情况下表现依然足够好。
缺点：在读写比例差不多的情况下，旋转操作过多。

# 红黑树(RB树)

AVL树的改进，引入着色规则，通过旋转和着色操作保证所有子树高度差不超过2。Map可以通过红黑树实现。

优点：写性能更高。
缺点：查询性能弱于AVL树，因为子树高度差比AVL多一层，最差情况会多一次比较。

# B-树(B-Tree, B树)

多路搜索树，又称B树，用于数据索引，子节点内放指针和数据块。通过分裂操作维持树结构。

# B+树

B-树改进型，子节点内不放数据块，统一放在叶节点内。查询性能稳定，IO数据利用率高。

# B*树

B+树改进型，增加子节点间指针，如果兄弟节点数据未满，则将一部分指针移到兄弟节点，并修改父节点关键字，将结点的最低利用率从1/2提高到2/3。

# 堆

完全二叉树

插入：插入队尾，上浮，如果大于parent则交换
删除：删除堆顶元素，用队尾元素替换，下沉，如果小于子节点中较大的，则交换
替换：先删除再插入
堆化：将数组当作完全二叉树，依次对所有非叶子结点下沉

# 实践

# 二叉树的前序遍历

二叉树的前序遍历

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func traverse(n *TreeNode, result *[]int) {
    if n == nil { return }
    *result = append(*result, n.Val)
    traverse(n.Left, result)
    traverse(n.Right, result)
}

func preorderTraversal(root *TreeNode) []int {
    result := []int{}
    traverse(root, &result)
    return result
}

//

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    result := []int{}
    if root == nil { return result }
    result = append(result, root.Val)
    result = append(result, preorderTraversal(root.Left)...)
    result = append(result, preorderTraversal(root.Right)...)
    return result
}

迭代

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    result := []int{}
    if root != nil {
        stack = append(stack, root)
    }
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if node != nil {
            if node.Right != nil {
                stack = append(stack, node.Right)
            }
            if node.Left != nil {
                stack = append(stack, node.Left)
            }
            stack = append(stack, node)
            stack = append(stack, nil)
        } else {
            node = stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            result = append(result, node.Val)
        }
    }
    return result
}

# 二叉树的后序遍历

二叉树的后序遍历

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    result := []int{}
    if root == nil { return result }
    result = append(result, postorderTraversal(root.Left)...)
    result = append(result, postorderTraversal(root.Right)...)
    result = append(result, root.Val)
    return result
}

迭代

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    result := []int{}
    if root != nil {
        stack = append(stack, root)
    }
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if node != nil {
            stack = append(stack, node)
            stack = append(stack, nil)
            if node.Right != nil {
                stack = append(stack, node.Right)
            }
            if node.Left != nil {
                stack = append(stack, node.Left)
            }
        } else {
            node = stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            result = append(result, node.Val)
        }
    }
    return result
}

# 二叉树的中序遍历

二叉树的中序遍历

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    result := []int{}
    if root == nil { return result }
    result = append(result, inorderTraversal(root.Left)...)
    result = append(result, root.Val)
    result = append(result, inorderTraversal(root.Right)...)
    return result
}

迭代

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    result := []int{}
    if root != nil {
        stack = append(stack, root)
    }
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if node != nil {
            if node.Right != nil {
                stack = append(stack, node.Right)
            }
            stack = append(stack, node)
            stack = append(stack, nil)
            if node.Left != nil {
                stack = append(stack, node.Left)
            }
        } else {
            node = stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            result = append(result, node.Val)
        }
    }
    return result
}

C++ 版本

void preorder(TreeNode* root, vector<int>& v) {
    if (root == nullptr) return;
    
    v.push_back(root->val);
    preorder(root->left, v);
    preorder(root->right, v);
}

void postorder(TreeNode* root, vector<int>& v) {
    if (root == nullptr) return;

    postorder(root->left, v);
    postorder(root->right, v);
    v.push_back(root->val);
}

void midorder(TreeNode* root, vector<int>& v) {
    if (root == nullptr) return;

    midorder(root->left, v);
    v.push_back(root->val);
    midorder(root->right, v);
}

void preorderIter(TreeNode* root, vector<int>& v) {
    std::stack<TreeNode*> s;
    
    if (root != nullptr) {
        s.push(root);
    }
    
    TreeNode* node = nullptr;
    while(s.size() > 0) {
        node = s.top();
        s.pop();
        if (node) {
            if (node->right) {
                s.push(node->right);
            }
            if (node->left) {
                s.push(node->left);
            }
            s.push(node);
            s.push(nullptr);
        } else {
            node = s.top();
            s.pop();
            v.push_back(node->val);
        }
    }
}

void postorderIter(TreeNode* root, vector<int>& v) {
    std::stack<TreeNode*> s;
    
    if (root != nullptr) {
        s.push(root);
    }
    
    TreeNode* node = nullptr;
    while(s.size() > 0) {
        node = s.top();
        s.pop();
        if (node) {
            s.push(node);
            s.push(nullptr);
            if (node->right) {
                s.push(node->right);
            }
            if (node->left) {
                s.push(node->left);
            }
        } else {
            node = s.top();
            s.pop();
            v.push_back(node->val);
        }
    }
}

void inorderIter(TreeNode* root, vector<int>& v) {
    std::stack<TreeNode*> s;
    
    if (root != nullptr) {
        s.push(root);
    }
    
    TreeNode* node = nullptr;
    while(s.size() > 0) {
        node = s.top();
        s.pop();
        if (node) {
            if (node->right) {
                s.push(node->right);
            }
            s.push(node);
            s.push(nullptr);
            if (node->left) {
                s.push(node->left);
            }
        } else {
            node = s.top();
            s.pop();
            v.push_back(node->val);
        }
    }
}

# 二叉树的层序遍历

二叉树的层序遍历

队列先进先出

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    queue := []*TreeNode{}
    result := [][]int{}
    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        size := len(queue)
        vec := []int{}
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            vec = append(vec, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, vec)
    }
    return result
}

# 二叉树的层序遍历II

二叉树的层序遍历II

同二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) [][]int {
    queue := []*TreeNode{}
    result := [][]int{}
    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        size := len(queue)
        vec := []int{}
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            vec = append(vec, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, vec)
    }
    for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
        result[i], result[j] = result[j], result[i]
    }
    return result
}

# 层序遍历获取二叉树的右视图

二叉树的右视图

同二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    queue := []*TreeNode{}
    result := []int{}
    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if i == size - 1 {
                result = append(result, node.Val)
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return result
}

# 层序遍历获取二叉树的层平均值

二叉树的层平均值

同二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func averageOfLevels(root *TreeNode) []float64 {
    result := []float64{}
    if root == nil {
        return result
    }
    queue := list.New()
    queue.PushBack(root)
    for queue.Len() > 0 {
        size := queue.Len()
        sum := 0
        for i := 0; i < size; i++ {
            node := queue.Front()
            queue.Remove(node)
            t := node.Value.(*TreeNode)
            sum += t.Val
            if t.Left != nil {
                queue.PushBack(t.Left)
            }
            if t.Right != nil {
                queue.PushBack(t.Right)
            }
        }
        result = append(result, float64(sum) / float64(size))
    }
    return result
}

# 层序遍历获取N叉树的层序遍历

N叉树的层序遍历

同二叉树的层序遍历

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func levelOrder(root *Node) [][]int {
    queue := []*Node{}
    result := [][]int{}
    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        size := len(queue)
        vec := []int{}
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            vec = append(vec, node.Val)
            for _, n := range node.Children {
                queue = append(queue, n)
            }
        }
        result = append(result, vec)
    }
    return result
}

# 前序遍历二叉树展开为链表

二叉树展开为链表

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode)  {
    stack := []*TreeNode{}
    list := []*TreeNode{}
    node := root
    for node != nil || len(stack) > 0 {
        for node != nil {
            list = append(list, node)
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack) - 1]
        node = node.Right
        stack = stack[:len(stack) - 1]
    }

    for i := 1; i < len(list); i++ {
        prev, curr := list[i-1], list[i]
        prev.Left, prev.Right = nil, curr
    }
}

# 翻转二叉树

翻转二叉树

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

迭代

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    stack := []*TreeNode{}
    stack = append(stack, root)
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        node.Left, node.Right = node.Right, node.Left
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }
    return root
}

层序

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    queue := []*TreeNode{}
    if root == nil {
        return root
    }
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            node.Left, node.Right = node.Right, node.Left
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return root
}

# 对称二叉树

对称二叉树

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func compare(left *TreeNode, right *TreeNode) bool {
    if right != nil && left == nil { return false }
    if right == nil && left != nil { return false }
    if right == nil && left == nil { return true }
    if right.Val != left.Val { return false }

    outside := compare(left.Left, right.Right)
    inside := compare(left.Right, right.Left)
    return outside && inside
}

func isSymmetric(root *TreeNode) bool {
    if root == nil { return true }
    return compare(root.Left, root.Right)
}

迭代，队列和栈均可

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil { return true }
    queue := []*TreeNode{}
    queue = append(queue, root.Left)
    queue = append(queue, root.Right)

    for len(queue) > 0 {
        left := queue[0]; queue = queue[1:]
        right := queue[0]; queue = queue[1:]
        if left == nil && right == nil {
            continue
        }
        if left == nil || right == nil || left.Val != right.Val {
            return false
        }
        queue = append(queue, left.Left)
        queue = append(queue, right.Right)
        queue = append(queue, left.Right)
        queue = append(queue, right.Left)
    }
    return true
}

# 二叉树的最大深度

二叉树的最大深度

后序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func Max(x, y int) int {
    if x < y { return y }
    return x
}

func depth(node *TreeNode) int {
    if node == nil { return 0 }
    return 1 + Max(depth(node.Left), depth(node.Right))
}

func maxDepth(root *TreeNode) int {
    return depth(root)
}

层序遍历

# N叉树的最大深度

N叉树的最大深度

迭代，同二叉树
层序遍历

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func maxDepth(root *Node) int {
    queue := []*Node{}
    depth := 0
    if root == nil { return depth }
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)
        depth++
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            for _, n := range node.Children {
                if n != nil {
                    queue = append(queue, n)
                }
            }
        }
    }
    return depth
}

# 二叉树的最小深度

二叉树的最小深度

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func Min(x, y int) int {
    if x > y { return y }
    return x
}

func depth(node *TreeNode) int {
    if node == nil { return 0 }
    leftDepth := depth(node.Left)
    rightDepth := depth(node.Right)

    if node.Left == nil && node.Right != nil {
        return 1 + rightDepth
    }

    if node.Right == nil && node.Left != nil {
        return 1 + leftDepth
    }

    return 1 + Min(leftDepth, rightDepth)
}


func minDepth(root *TreeNode) int {
    return depth(root)
}

层序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    queue := []*TreeNode{}
    depth := 0
    if root == nil { return depth }
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)
        depth++
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left == nil && node.Right == nil {
                return depth
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return depth
}

# 完全二叉树的节点数

完全二叉树的节点个数

前序遍历递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func nodeNum(node *TreeNode) int {
    if node == nil { return 0 }
    return 1 + nodeNum(node.Left) + nodeNum(node.Right)
}

func countNodes(root *TreeNode) int {
    return nodeNum(root)
}

层序遍历迭代

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countNodes(root *TreeNode) int {
    queue := []*TreeNode{}
    count := 0
    if root == nil { return count }
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            count++
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return count
}

# 平衡二叉树

平衡二叉树

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func Max(x, y int) int {
    if x > y { return x }
    return y
}

func depth(node *TreeNode) int {
    if node == nil { return 0 }
    leftDepth := depth(node.Left)
    if leftDepth < 0 { return -1 }
    rightDepth := depth(node.Right)
    if rightDepth < 0 { return -1 }
    if math.Abs(float64(leftDepth) - float64(rightDepth)) > 1 {
        return -1
    }
    return 1 + Max(leftDepth, rightDepth)
}

func isBalanced(root *TreeNode) bool {
    return depth(root) >= 0
}

# 二叉树的所有路径

二叉树的所有路径

前序遍历递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func path(node *TreeNode, pathStr string) []string {
    results := []string{}
    pathStr += strconv.Itoa(node.Val)
    if node.Left == nil && node.Right == nil {
        results = append(results, pathStr)
    }
    pathStr += "->"
    if node.Left != nil {
        results = append(results, path(node.Left, pathStr)...)
    }
    if node.Right != nil {
        results = append(results, path(node.Right, pathStr)...)
    }
    return results
}

func binaryTreePaths(root *TreeNode) []string {
    if root == nil { return []string{} }
    return path(root, "")
}

# 相同的树

相同的树

递归，同对称树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p != nil && q == nil { return false }
    if p == nil && q != nil { return false }
    if p == nil && q == nil { return true }
    if p.Val != q.Val { return false }

    left := isSameTree(p.Left, q.Left)
    right := isSameTree(p.Right, q.Right)
    return left && right
}

迭代，队列和栈均可，同对称树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    queue := []*TreeNode{}
    queue = append(queue, p)
    queue = append(queue, q)
    for len(queue) > 0 {
        left := queue[0]; queue = queue[1:]
        right := queue[0]; queue = queue[1:]
        if left == nil && right == nil {
            continue
        }
        if left == nil || right == nil || left.Val != right.Val {
            return false
        }
        queue = append(queue, left.Left)
        queue = append(queue, right.Left)
        queue = append(queue, left.Right)
        queue = append(queue, right.Right)
    }
    return true
}

# 左叶子之和

左叶子之和

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
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
    }
    return sum + sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}

# 找树左下角的值

找树左下角的值

层序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    queue := []*TreeNode{root}
    result := 0
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if i == 0 { result = node.Val }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return result
}

# 路径总和

路径总和

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil { return false }
    if root.Left == nil && root.Right == nil && root.Val == targetSum {
        return true
    }
    nextSum := targetSum - root.Val
    return hasPathSum(root.Left, nextSum) || hasPathSum(root.Right, nextSum)
}

# 路径总和II

路径总和II

递归，注意Go的引用

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func traverse(root *TreeNode, targetSum int, res *[][]int, path[]int) {
    path = append(path, root.Val)
    nextSum := targetSum - root.Val
    if root.Left == nil && root.Right == nil {
        if nextSum == 0 {
            tmp := make([]int, len(path))
            copy(tmp, path)
            *res = append(*res, tmp)
        }
        return
    }

    if root.Left != nil {
        traverse(root.Left, nextSum, res, path)
    }
    if root.Right != nil {
        traverse(root.Right, nextSum, res, path)
    }
}

func pathSum(root *TreeNode, targetSum int) [][]int {
    result := [][]int{}
    path := []int{}
    if root == nil { return result }
    traverse(root, targetSum, &result, path)
    return result
}

# 从中序与后序遍历序列构造二叉树

从中序与后序遍历序列构造二叉树

先取后序遍历最后一个值作为当前根节点，从中序遍历比对确定左右子树切割位置，后序遍历子树大小应和中序遍历数组子序列一致，将切分出的左右子序列递归。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type TreeBuilder struct {
    inorder []int
    postorder []int
}

func (t TreeBuilder)traverse(inStart, inEnd, poStart, poEnd int) *TreeNode {
    if poStart == poEnd { return nil }
    rootVal := t.postorder[poEnd - 1]
    root := &TreeNode{Val: rootVal}
    if poEnd - poStart == 1 { return root }

    var inMid int
    for inMid = inStart; inMid < inEnd; inMid++ {
        if t.inorder[inMid] == rootVal { break }
    }

    poMid := poStart + inMid - inStart
    root.Left = t.traverse(inStart, inMid, poStart, poMid)
    root.Right = t.traverse(inMid + 1, inEnd, poMid, poEnd - 1)
    return root
}

func buildTree(inorder []int, postorder []int) *TreeNode {
    return TreeBuilder{inorder, postorder}.traverse(0, len(inorder), 0, len(postorder))
}

# 从中序与前序遍历序列构造二叉树

从中序与前序遍历序列构造二叉树

类似后序+中序

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type TreeBuilder struct {
    inorder []int
    preorder []int
}

func (t TreeBuilder)traverse(inStart, inEnd, prStart, prEnd int) *TreeNode {
    // fmt.Printf("%v %v | %v %v \n", inStart, inEnd, prStart, prEnd)

    if prStart == prEnd { return nil }
    rootVal := t.preorder[prStart]
    root := &TreeNode{Val: rootVal}
    if prEnd - prStart == 1 { return root }

    var inMid int
    for inMid = inStart; inMid < inEnd; inMid++ {
        if t.inorder[inMid] == rootVal { break }
    }

    prMid := prStart + 1 + inMid - inStart
    root.Left = t.traverse(inStart, inMid, prStart + 1, prMid)
    root.Right = t.traverse(inMid + 1, inEnd, prMid, prEnd)
    return root
}

func buildTree(preorder []int, inorder []int) *TreeNode {
    return TreeBuilder{inorder, preorder}.traverse(0, len(inorder), 0, len(preorder))
}

改写成slice更简洁

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    // fmt.Printf("%v | %v \n", preorder, inorder)
    if len(preorder) == 0 { return nil }
    rootVal := preorder[0]
    root := &TreeNode{Val: rootVal}
    if len(preorder) == 1 { return root }

    var inMid int
    for inMid = 0; inMid < len(inorder); inMid++ {
        if inorder[inMid] == rootVal { break }
    }

    root.Left = buildTree(preorder[1:1+inMid], inorder[:inMid])
    root.Right = buildTree(preorder[1+inMid:], inorder[inMid+1:])
    return root
}

# 最大二叉树

最大二叉树

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 { return nil }
    max := nums[0]
    index := 0
    for i, v := range nums {
        if v > max { 
            max = v
            index = i
        }
    }
    root := &TreeNode{Val: max}
    root.Left = constructMaximumBinaryTree(nums[:index])
    root.Right = constructMaximumBinaryTree(nums[index+1:])
    return root
}

# 合并二叉树

合并二叉树

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil { return root2 }
    if root2 == nil { return root1 }
    root1.Val += root2.Val
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)
    return root1
}

# 二叉搜索树中的搜索

二叉搜索树中的搜索

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil { return nil }
    if root.Val > val { return searchBST(root.Left, val) }
    if root.Val < val { return searchBST(root.Right, val) }
    return root
}

迭代

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    for root != nil {
        if root.Val > val { 
            root = root.Left
        } else if root.Val < val {
            root = root.Right
        } else {
            return root
        }
    }
    return nil
}

# 验证二叉搜索树

验证二叉搜索树

递归，注意子树区间必须，需要上下界来判断

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isValidBST(root *TreeNode) bool {
    return helper(root, math.MinInt64, math.MaxInt64)
}

func helper(root *TreeNode, lower, upper int) bool {
    if root == nil {
        return true
    }
    if root.Val <= lower || root.Val >= upper {
        return false
    }
    return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
}

中序遍历，序列递增

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isValidBST(root *TreeNode) bool {
    valid, _ := traverse(root, math.MinInt64)
    return valid
}

func traverse(root *TreeNode, val int) (bool, int) {
    if root == nil {
        return true, val
    }
    var valid bool
    valid, val = traverse(root.Left, val)
    if !valid {
        return false, val
    }

    if root.Val <= val {
        return false, val
    }
    val = root.Val

    valid, val = traverse(root.Right, val)
    if !valid {
        return false, val
    }
    return true, val
}

# 二叉搜索树的最小绝对差

二叉搜索树的最小绝对差

中序遍历，Go的struct指针

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type Searcher struct {
    min int
    last int
}

func Abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func (s *Searcher)traverse(root *TreeNode) {
    if root == nil { return }
    s.traverse(root.Left)
    val := Abs(root.Val - s.last)
    if val < s.min {
        s.min = val
    }
    s.last = root.Val
    s.traverse(root.Right)
}

func getMinimumDifference(root *TreeNode) int {
    s := Searcher{math.MaxInt64, math.MaxInt64}
    s.traverse(root)
    return s.min
}

# 二叉搜索树中的众数

二叉搜索树中的众数

二叉搜索树中序遍历有序

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type Searcher struct {
    Last int
    Count int
    MaxCount int
    Modes []int
}

func (s *Searcher)traverse(root *TreeNode) {
    if root == nil { return }
    s.traverse(root.Left)
    if root.Val == s.Last {
        s.Count++
    } else {
        s.Last = root.Val
        s.Count = 1
    }
    if s.Count > s.MaxCount {
        s.Modes = nil
        s.Modes = append(s.Modes, root.Val)
        s.MaxCount = s.Count
    } else if s.Count == s.MaxCount {
        s.Modes = append(s.Modes, root.Val)
    }
    s.traverse(root.Right)
}

func findMode(root *TreeNode) []int {
    s := Searcher{
        Last: 0,
        Count: 0,
        MaxCount: 0,
    }
    s.traverse(root)
    return s.Modes
}

# 二叉树的最近公共祖先

二叉树的最近公共祖先

递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
     if root == nil { return nil }
     if root.Val == p.Val || root.Val == q.Val {
         return root
     }
     left := lowestCommonAncestor(root.Left, p, q)
     right := lowestCommonAncestor(root.Right, p, q)
     if left != nil && right != nil { return root }
     if left != nil && right == nil { return left }
     if left == nil && right != nil { return right }
     return nil
}

# 二叉搜索树的最近公共祖先

二叉搜索树的最近公共祖先

二叉搜索树有序，前序遍历，第一个落在[p, q]或[q, p]区间的就是公共祖先

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  if root.Val > p.Val && root.Val > q.Val {
        return lowestCommonAncestor(root.Left, p, q)
    }
    if root.Val < p.Val && root.Val < q.Val {
        return lowestCommonAncestor(root.Right, p, q)
    }
    return root
}

迭代

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    for {
        if root.Val > p.Val && root.Val > q.Val {
            root = root.Left
        } else if root.Val < p.Val && root.Val < q.Val {
            root = root.Right
        } else {
            return root
        }
    }
}

# 二叉搜索树中的插入操作

二叉搜索树中的插入操作

利用二叉搜索树的性质插入

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }
    if val < root.Val {
        root.Left = insertIntoBST(root.Left, val)
    }
    if val > root.Val {
        root.Right = insertIntoBST(root.Right, val)
    }
    return root
}

# 删除二叉搜索树中的节点

删除二叉搜索树中的节点

删除节点时分五种情况：
1. 找不到
2. 左右都为空，直接删除
3. 左空右不空，等于右
4. 右空左不空，等于左
5. 左右都不空，有两种方案
- 用右子树中最小的节点替换，退化为2，因为右子树中最小节点也一定比左子树中的任意节点都大，这个节点是右子树的最左叶子节点。可以统一2/3/5。
- 把左子树挂在右子树的最左叶子节点，退化为3

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil { return root }
    if root.Val == key {
        if root.Right == nil {
            return root.Left
        }
        cur := root.Right
        for cur.Left != nil {
            cur = cur.Left
        }
        root.Val, cur.Val = cur.Val, root.Val
    }
    root.Left = deleteNode(root.Left, key)
    root.Right = deleteNode(root.Right, key)
    return root
}

# 修剪二叉搜索树

修剪二叉搜索树

前序遍历，如果节点值小于下界，左子树一定都小于下界，右子树不一定，可以先把右子树替换当前节点，递归判断。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func trimBST(root *TreeNode, low int, high int) *TreeNode {
    if root == nil { return root }
    if root.Val < low {
        return trimBST(root.Right, low, high)
    }
    if root.Val > high {
        return trimBST(root.Left, low, high)
    }
    root.Left = trimBST(root.Left, low, high)
    root.Right = trimBST(root.Right, low, high)
    return root
}

# 将有序数组转换为二叉搜索树

将有序数组转换为二叉搜索树

利用二叉搜索树有序特性，二分数组

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 { return nil }
    mid := len(nums) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left = sortedArrayToBST(nums[:mid])
    root.Right = sortedArrayToBST(nums[mid+1:])
    return root
}

# 把二叉搜索树转换为累加树

把二叉搜索树转换为累加树

反中序遍历累加即可

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func traverse(root *TreeNode, val int) int {
    if root == nil { return val }
    val = traverse(root.Right, val)
    root.Val += val
    val = root.Val
    val = traverse(root.Left, val)
    return val
}

func convertBST(root *TreeNode) *TreeNode {
    traverse(root, 0)
    return root
}

Previous post: 算法基础 - 数组 Next post: 算法基础 - 排序

吹拉弹唱