数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

春节7天练 | Day 5:二叉树和堆

王争 2019-02-09
你好,我是王争。春节假期进入尾声了。你现在是否已经准备返回工作岗位了呢?今天更新的是测试题的第五篇,我们继续来复习。

关于二叉树和堆的 7 个必知必会的代码实现

二叉树

实现一个二叉查找树,并且支持插入、删除、查找操作
实现查找二叉查找树中某个节点的后继、前驱节点
实现二叉树前、中、后序以及按层遍历

实现一个小顶堆、大顶堆、优先级队列
实现堆排序
利用优先级队列合并 K 个有序数组
求一组动态数据集合的最大 Top K

对应的 LeetCode 练习题(@Smallfly 整理)

Invert Binary Tree(翻转二叉树)
Maximum Depth of Binary Tree(二叉树的最大深度)
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(29)

  • 李皮皮皮皮皮
    平衡树的各种操作太烧脑了,左旋右旋,红黑树就更别提了。过段时间就忘。😢
    2019-02-09
    8
  • kai
    树的前中后序遍历-递归实现:

    public class TreeTraversal {

        public static class Node {
            public int value;
            public Node left;
            public Node right;

            public Node(int value) {
                this.value = value;
            }
        }

        // 二叉树的递归遍历
        public static void preOrderRecursive(Node head) {
            if (head == null) {
                return;
            }

            System.out.print(head.value + " ");
            preOrderRecursive(head.left);
            preOrderRecursive(head.right);
        }

        public static void inOrderRecursive(Node head) {
            if (head == null) {
                return;
            }

            inOrderRecursive(head.left);
            System.out.print(head.value + " ");
            inOrderRecursive(head.right);
        }

        public static void postOrderRecursive(Node head) {
            if (head == null) {
                return;
            }

            postOrderRecursive(head.left);
            postOrderRecursive(head.right);
            System.out.print(head.value + " ");
        }

    }
    2019-02-11
    2
  • kai
    树的前中后序遍历-非递归实现:
    import java.util.Stack;


    public class TreeTraversal {
        public static class Node {
            public int value;
            public Node left;
            public Node right;
            public Node(int value) {
                this.value = value;
            }
        }
        // 二叉树的非递归遍历
        public static void preOrder(Node head) {
            System.out.print("pre-order: ");
            if (head == null) {
                return;
            }
            Stack<Node> s = new Stack<>();
            s.push(head);
            while (!s.isEmpty()) {
                head = s.pop();
                System.out.print(head.value + " ");
                if (head.right != null) {
                    s.push(head.right);
                }

                if (head.left != null) {
                    s.push(head.left);
                }
            }
            System.out.println();
        }

        public static void inOrder(Node head) {
            System.out.print("in-order: ");
            if (head == null) {
                return;
            }
            Stack<Node> s = new Stack<>();
            while (!s.isEmpty() || head != null) {
                if (head != null) {
                    s.push(head);
                    head = head.left;
                } else {
                    head = s.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
            System.out.println();
        }

        public static void postOrder(Node head) {
            System.out.print("pos-order: ");
            if (head == null) {
                return;
            }

            Stack<Node> tmp = new Stack<>();
            Stack<Node> s = new Stack<>();

            tmp.push(head);
            while(!tmp.isEmpty()) {
                head = tmp.pop();
                s.push(head);

                if (head.left != null) {
                    tmp.push(head.left);
                }

                if (head.right != null) {
                    tmp.push(head.right);
                }
            }

            while (!s.isEmpty()) {
                System.out.print(s.pop().value + " ");
            }

            System.out.println();
        }
    }
    2019-02-11
    1
  • kai
    今天看了一下这一节的题目,发现校招面试的时候都考过,今天又刷了一下,总结了一波,相应的知识点也总结了一下~
    2019-02-10
    1
  • 纯洁的憎恶
    今天的题目很适合递归实现,当然递归公式离代码实现还是存在一定距离。
    1.翻转二叉树(T){
    当T为Null时则返回;
    翻转二叉树(T的左子树);
    翻转二叉树(T的右子树);
    若T不为叶节点,则交换T的左右子树位置;


    2.最大深度(T){
    当T为Null时,return 0;
    return Max(最大深度(T左子树)+1,最大深度(T右子树)+1);

    函数返回值即为最大深度。

    3.验证二叉查找树(T,&最大值,&最小值){
    当T为Null时,return true;
    当T为叶节点时,最小值=最大值=当前节点,返回true;
    左最大值=左最小值=T的值;
    验证二叉查找树(T的左子树,&左最大值,&左最小值);
    右最大值=右最小值=T的值;
    验证(T的右子树,&右最大值,&右最小值);
    T的值小于等于右最小值,并且大于等于左最大值时,最大值=右最大值,最小值=左最小值,之后返回true,否则返回false并结束。

    函数最终返回true则验证成功。

    4.计算路径和(T,sum){
    若T为Null返回false;
    若T是叶节点,如果sum+T的值=目标值则返回true并结束,否则返回false;
    计算路径和(T的左子树,sum+T的值);
    计算路径和(T的右子树,sum+T的值);

    计算路径和(T,0)返回true时则存在于目标值相同的路径之和;
    2019-02-10
    1
  • _CountingStars
    二叉树的最大深度 go 语言实现
    /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     * Val int
     * Left *TreeNode
     * Right *TreeNode
     * }
     */
    func maxDepth(root *TreeNode) int {
        if root == nil {
            return 0
        }
        
        leftDepth :=0
        rightDepth :=0
        if root.Left != nil {
            leftDepth = maxDepth(root.Left)
        }
        
        if root.Right != nil {
            rightDepth = maxDepth(root.Right)
        }
        
        if leftDepth >= rightDepth {
            return leftDepth + 1
        } else {
            return rightDepth + 1
        }
    }
    2019-02-09
    1
  • 失火的夏天
    // 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
            if(root == null){
    return root;
    }
    TreeNode node = root;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(node);
    while(!queue.isEmpty()){
    node = queue.poll();
    TreeNode tempNode = node.left;
    node.left = node.right;
    node.right = tempNode;
    if(node.left != null){
    queue.offer(node.left);
    }
    if(node.right != null){
    queue.offer(node.right);
    }
    }
            return root;
        }
    // 二叉树的最大深度
    public int maxDepth(TreeNode root) {
            if(root == null) return 0;
            return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
        }
    // 验证二叉查找树
    public boolean isValidBST(TreeNode root) {
            if (root == null) {
    return true;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    TreeNode preNode = null;
    while(node != null || !stack.isEmpty()){
    stack.push(node);
    node = node.left;
    while(node == null && !stack.isEmpty()){
    node = stack.pop();
    if(preNode != null){
    if(preNode.val >= node.val){
    return false;
    }
    }
    preNode = node;
    node = node.right;
    }
    }
            return true;
        }
    // 路径总和
    public boolean hasPathSum(TreeNode root, int sum) {
            if (root == null) {
                return false;
            }
            return hasPathSum(root, root.val, sum);
        }

        public boolean hasPathSum(TreeNode root, int tmp, int sum) {
            if (root == null) {
                return false;
            }
            if (root.left == null && root.right == null) {
                return tmp == sum;
            }
            if (root.left == null) {
                return hasPathSum(root.right, root.right.val + tmp, sum);
            }
            if (root.right == null) {
                return hasPathSum(root.left, root.left.val + tmp, sum);
            }
            return hasPathSum(root.left, root.left.val + tmp, sum) ||
                    hasPathSum(root.right, root.right.val + tmp, sum);
        }

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-09
    1
  • 啵啵啵
    作者可以提供pdf版的课程资料吗,不然我觉得不值,因为不能大量复制,不能形成书面笔记,毕竟我付费了。

    作者回复: 要不要保时捷也送你一辆啊

    2019-10-06
  • 懒猫
    打卡
    2019-06-14
  • 付坤
    https://github.com/DigDeeply/data-structures-learning/blob/0e14f4f69d1f3d45c3d16820cb771f6c242898e4/57-5-binary_tree/binary_tree.go

    用数组实现的二叉查找树,支持增删查。
    2019-04-01
  • hopeful
    #验证二叉搜索树
    def isValidBST(self, root: TreeNode) -> bool:
            def inorderTraversal(root):
                if root == None:
                    return []
                res = []
                res += inorderTraversal(root.left)
                res.append(root.val)
                res += inorderTraversal(root.right)
                return res
     
            res = inorderTraversal(root)
            if res != sorted(list(set(res))): return False
            return True
    2019-03-11
  • hopeful
    #实现小顶堆
    def makeSmallHeap(array):
        for i in range(int(len(array)/2) , -1 , -1):
            makeHeap(array , i , len(array))
    def makeHeap(array , i ,N):
        while 2*i+1 < N:
            child = 2*i+1
            if child != N-1 and array[child] > array[child+1]:
                child+=1
            if array[child] < array[i]:
                temp = array[child]
                array[child] = array[i]
                array[i] = temp
                i = child
            else:
                break
    2019-03-05
  • hopeful
    #实现大顶堆
    def makeBigHeap(array):
        for i in range(int(len(array)/2) , -1 , -1):
            makeHeap(array , i , len(array))
    def makeHeap(array , i ,N):
        while 2*i+1 < N:
            child = 2*i+1
            if child != N-1 and array[child] < array[child+1]:
                child+=1
            if array[child] > array[i]:
                temp = array[child]
                array[child] = array[i]
                array[i] = temp
                i = child
            else:
                break
    2019-03-05
  • hopeful
    #堆排序
    import random
    import time

    def Array(n):
        a = []
        for i in range(n):
            a.append(random.randint(0 , n))
        return a

    def makeHeap(array , i ,N):
        while 2*i+1 < N:
            child = 2*i+1
            if child != N-1 and array[child] < array[child+1]:
                child+=1
            if array[child] > array[i]:
                temp = array[child]
                array[child] = array[i]
                array[i] = temp
                i = child
            else:
                break
    def heapSort():
        array = Array(100)
        for i in range(int(len(array)/2) , -1 , -1):
            makeHeap(array , i , len(array))
        for i in range(len(array)-1 , -1 , -1):
            temp = array[0]
            array[0] = array[i]
            array[i] = temp
            makeHeap(array , 0 , i)
        print(array)
    2019-03-05
  • Sharry
    路径总和: 使用回溯法, 遍历每一条 root->leaf 的路线是否满足在和为 sum, 可以使用减枝操作

    二叉树深度 = 左右子树中深度最大者 + 1

    验证二叉搜索树:
    1. 遍历每一个结点, 若都满足, 当前结点大于左子树中的最大值, 小于右子树中的最小值, 则说明为二叉搜索树
    2. 中序遍历二叉搜索树, 若序列递增, 则说明为二叉搜索树
    2019-02-25
  • hopeful
    #二叉树前中后序及层次遍历非递归版本
    class Tree:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None

    #----前序----
    def preOrder(Tree T):
        if T is None:
            return []
        list1 = []
        list2 = []
        list1.append(T)
        while len(list1) > 0:
            t = list1.pop()
            list2.append(t)
            if t.right not None:
                list1.append(t.right)
            if t.left not None:
                list1.append(t.left)
        return list2

    #----中序----
    def inOrder(Tree T):
        if T is None:
            return []
        list1 = []
        list2 = []
        while T or len(list1)>0 :
            if T :
                list1.append(T)
                T = T.left
            else:
                T = list1.pop()
                list2.append(T)
                T = T.right
        return list2

    #----后序----
    def postOrder(Tree T):
        if T is None:
            return []
        list1 = []
        list2 = []
        list1.append(T)
        while len(list1)>0 :
            t = list1.pop()
            list2.append(t)
            if t.left not None:
                list1.append(t.left)
            if t.right not None:
                list1.append(t.right)
        return list2[::-1]

    #----层次-----
    def levelOrder():
        if T is None:
            return []
        list1 = []
        list2 = []
        list1.append(T)
        while len(list1)>0 :
            t = list1[0]
            del list1[0]
            list2.append(t)
            if t.left not None:
                list1.append(t.left)
            if t.right not None:
                list1.append(t.right)
        return list2
    2019-02-16
  • abner
    java实现二叉树前序、中序、后序和层次遍历
    代码如下:
    package tree;

    import java.util.LinkedList;
    import java.util.Queue;

    public class BinaryTree {
        
        private Node root = null;
        
        public static class Node {
            
            private String data;
            private Node left;
            private Node right;
            
            public Node(String data, Node left, Node right) {
                this.data = data;
                this.left = left;
                this.right = right;
            }
        }
        
        public void preOrder(Node root) {
            if (null == root) {
                return ;
            }
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
        
        public void inOrder(Node root) {
            if (null == root) {
                return ;
            }
            inOrder(root.left);
            System.out.print(root.data + " ");
            inOrder(root.right);
        }
        
        public void postOrder(Node root) {
            if (null == root) {
                return ;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.data + " ");
        }
        
        public void traverseByLayer(Node root) {
            if (null == root) {
                return ;
            }
            Queue<Node> queue = new LinkedList<Node>();
            queue.add(root);
            while (!queue.isEmpty()) {
                Node pNode = queue.peek();
                System.out.print(pNode.data + " ");
                queue.poll();
                if (root.left != null) {
                    queue.add(root.left);
                }
                if (root.right != null) {
                    queue.add(root.right);
                }
            }
        }
    }
    2019-02-14
  • 拉欧
    Path Sum(路径总和)go 语言实现
    func hasPathSum(root *TreeNode, sum int) bool {

    if root==nil{
    return false
    }
    if root.Left==nil && root.Right==nil{
    if root.Val==sum{
    return true
    }else{
    return false
    }

    }
    left:=false
    if root.Left!=nil{
    left=hasPathSum(root.Left,sum-root.Val)
    }
    right:=false
    if root.Right!=nil{
    right=hasPathSum(root.Right,sum-root.Val)
    }
    return left || right
    }
    2019-02-14
  • 拉欧
    Validate Binary Search Tree(验证二叉查找数) go语言实现

    func isValidBST(root *TreeNode) bool {

    if root==nil{
    return true
    }
    less:=true
    more:=true
    if root.Left!=nil{
    less=JudgeLess(root.Left,root.Val)
    }
    if root.Right!=nil{
    more=JudgeMore(root.Right,root.Val)
    }
    if ! (less && more){
    return false
    }else{
    return isValidBST(root.Left) && isValidBST(root.Right)
    }
    }

    func JudgeLess(root *TreeNode,num int) bool{

    if root.Val>=num{
    return false
    }
    if root.Left!=nil && root.Right!=nil{
    return JudgeLess(root.Left,num) && JudgeLess(root.Right,num)
    }else if root.Left!=nil{
    return JudgeLess(root.Left,num)
    }else if root.Right!=nil{
    return JudgeLess(root.Right,num)
    }else{
    return true
    }
    }

    func JudgeMore(root *TreeNode,num int) bool{
    if root.Val<=num{
    return false
    }
    if root.Left!=nil && root.Right!=nil{
    return JudgeMore(root.Left,num) && JudgeMore(root.Right,num)
    }else if root.Left!=nil{
    return JudgeMore(root.Left,num)
    }else if root.Right!=nil{
    return JudgeMore(root.Right,num)
    }else{
    return true
    }
    }
    2019-02-14
  • 拉欧
    Invert Binary Tree(翻转二叉树) go 语言实现
    func invertTree(root *TreeNode) *TreeNode {
    if root==nil{
    return root
    }
    temp:=root.Left
    root.Left=root.Right
    root.Right=temp
    invertTree(root.Left)
    invertTree(root.Right)
    return root
    }
    2019-02-14
收起评论
29
返回
顶部