介绍trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。说白了,Trie树是一种N叉树,除根节点外,每个节点都保存了这...
介绍二叉查找树(英语:Binary Search Tree),也称为二叉查找树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;任意节点的左、右子树也分别为二叉查...
介绍层序遍历,顾名思义,不难理解,就是一层一层地遍历Golang实现此处分为递归实现(DFS,深度优先算法)和迭代实现(BFS,广度优先算法)本文以Leetcode102题为例:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/递归实现(DFS)递归实现需要储存每层的级数实现起来主要分为以下几个步骤递归跳出条...
介绍前序遍历前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。上图的树的前序遍历顺序:1->2->4->5->7->8->3->6->9中序遍历中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。上图的树的前序遍历顺序:4->2->7->5->8->3->9->6后序遍历后序遍历是先遍历左子树...