二叉树

先把二叉树的四种遍历模式和后果记录下来，而后倒推各种解法，如下图所示： 4种遍历模式的程序前序遍历：根、左、右中序遍历：左、根、右后序遍历：左、右、根档次遍历：一层一层遍历4种遍历模式及后果如下前序遍历：1 2 4 5 7 8 3 6中序遍历：4 2 7 5 8 1 3 6后序遍历：4 7 8 5 2 6 3 1档次遍历：1 2 3 4 5 6 7 8To Be Continueed...

简介中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序环游。 定义在二叉树中，中序遍历首先遍历左子树，而后拜访根结点，最初遍历右子树。若二叉树为空则完结返回，否则：（1）中序遍历左子树（2）拜访根结点（3）中序遍历右子树如图所示二叉树，中序遍历后果：DBEAFC Golang实现func (root *TreeNode) inorder()[]int{ res:=[]int{} if root==nil{ return res } stack:=[]*TreeNode{} for root!=nil || len(stack)!=0{ if root!=nil{ stack=append(stack,root) root=root.Lchild }else{ root=stack[len(stack)-1] res=append(res,root.data) stack=stack[:len(stack)-1] root=root.Rchild } } return res}

本篇文章以求二叉树中的最大值和最小值的最大差值为例，记录一下递归中遇到的问题，是递归时的参数问题，什么时候须要把变量放在参数中，什么时候须要把变量定义为全局变量。 变量定义为全局变量以上面的二叉树为例，求整棵树中的节点的值的最大差值，也就是求出最大值和最小值。 前序遍历的过程如下： 图中圆圈中记录的是结点的拜访程序，前序的遍历程序和拜访程序雷同。 走到结点 1 （遍历结点），记录下以后的最大值和最小值 [1, 1] （拜访结点），而后遍历左子树，遍历完左子树再右子树。 当走到节点 2 时，更新最大值和最小值时，是和 [1, 1] 比拟的，所以记录的最大值和最小值是 [2, 1]。 当走到节点 4 时，更新最大值和最小值时，是和 [2, 1] 比拟的，所以记录的最大值和最小值是 [4, 1]。 当走到节点 5 时，更新最大值和最小值时，是和 [4, 1] 比拟的，所以记录的最大值和最小值是 [5, 1]。 当走到节点 3 时，更新最大值和最小值时，是和 [5, 1] 比拟的，所以记录的最大值和最小值是 [5, 1]。 当走到节点 6 时，更新最大值和最小值时，是和 [5, 1] 比拟的，所以记录的最大值和最小值是 [6, 1]。 遍历完之后，从节点 4 回到 节点 2 的时候（回溯的时候），最大值和最小值也回到节点 2 时的值 [2, 1] 。所以当遍历的门路从 1-2-4 走到 1-2-5 时，节点5 更新最大值和最小值时，是和 [2, 1] 比拟的，而不是 [4, 1] 。 ...

摘要：日常生活中，很多事物都能够用树来形容，例如书的目录、工作单位的组织架构等等。树是计算机中十分重要的一种数据结构，树存储形式能够进步数据的存储、读取效率。本文分享自华为云社区《【云驻共创】想理解二叉树，看这篇文章就够了》，作者： liuzhen007 。 前言日常生活中，很多事物都能够用树来形容，例如书的目录、工作单位的组织架构等等。树是计算机中十分重要的一种数据结构，树存储形式能够进步数据的存储、读取效率。 一、树的根本定义日常生活中，很多事物都能够用树来形容，树是计算机中十分重要的一种数据结构，树存储形式能够进步数据的存储、读取效率，比方利用二叉排序树，既能够保证数据的检索速度，同时，也能够保证数据的插入、删除、批改的速度。 其实，树的品种有很多种，比方一般的二叉树、齐全二叉树、满二叉树、线索二叉树、哈夫曼树、二叉排序树、均衡二叉树、AVL均衡二叉树、红黑树、B树、B+树、堆等。明天介绍的次要内容是二叉树的基本知识和几种根底类型的二叉树。 二、二叉树的相干术语在正式开讲前，首先介绍一些对于二叉树的专业名词和术语，包含结点、结点的度、叶子结点、分支结点、结点的档次、树的度、树的深度等，理解这些根底的专业名词和术语对于咱们了解二叉树的个性有十分重要的帮忙作用。 1）结点：蕴含一个数据元素及若干指向子树分支的信息。 2）结点的度：一个结点领有子树的数据成为结点的度。 3）叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。 4）分支结点：也称为非终端结点，度不为零的结点成为非终端结点。 5）结点的档次：从根结点开始，根结点的档次为1，根的间接后继档次为2，以此类推。 6）树的度：树中所有结点的度的最大值。 7）树的深度：树中结点的最大档次。 1. 树的特点树作为一种非凡的数据结构，有十分多的个性，比方： 1）每个结点有多个或者零个子结点 2）没有父结点的结点成为根结点，没有子结点的结点成为叶结点 3）每一个非根结点只有一个父结点 4）每个结点及其后辈结点整体上能够看做是一棵树，称为以后结点为根的子树 2. 二叉树的根本定义1）二叉树就是度不超过2的树，其每个结点最多有两个子结点 2）二叉树的结点分为左结点和右结点 3. 满二叉树1）二叉树的每一层的结点度都达到最大值，则这个二叉树就是满二叉树 2）一棵深度为n的满二叉树，有2^n-1个结点 4. 齐全二叉树叶子结点只能呈现在最上层和次上层，最初一层的叶子结点在右边间断，倒数第二层的叶子结点在左边间断，咱们称为齐全二叉树。 三、二叉树的创立接下来，咱们通过代码来形容二叉树，语言以Java为例，其中结点类定义如下： 二叉查找树类定义如下： 相干类定义好后，咱们来看具体的办法实现，上面别离介绍。 1. size（）办法size（）办法绝对简略，每次增加元素加一，删除元素减一，保护一个公共的变量 num 即可，代码实现如下： 2. put（Key key，Value value）办法put（Key key，Value value）办法能够利用重载办法 put（Node x，Key key，Value value），因而实现也绝对简略，其中第一个参数只须要传根结点即可，代码实现如下： 3. put（Node x，Key key，Value value）办法put（Node x，Key key，Value value）办法应该是整个类中实现绝对较为简单的，上面进行简略的剖析。 第一种状况，以后树中没有任何一个结点，间接将新插入的结点作为根结点。 第二种状况，以后树不为空，则从根结点开始。这种状况有能够细分为三种状况： 1）如果新结点的key小于以后结点的key，则持续查找以后结点的左子结点。 2）如果新结点的key大于以后结点的key，则持续查找以后结点的右子结点。 3）如果新结点的key等于以后结点的key，则树中曾经存在这样的结点，替换该结点的value值即可。 具体的代码实现如下： 4. get（Key key）办法get（Key key）办法和 put（Key key，Value value）办法相似，也能够利用重载办法 get（Node x，Key key）来实现，代码实现如下： 5. get（Node x，Key key）办法get（Node x，Key key）办法实现查询方法从根结点开始，如果要查问的key小于以后结点的key，则持续找以后结点的左子结点；如果要查找的key大于以后结点的key，则持续找以后结点的右子结点；如果要查找的key等于以后结点的key，则返回以后结点的value。 ...

大家好，我是虫爸。在上一篇文章中一文弄懂二叉树的三种遍历形式，别离从递归和非递归的角度，解说、剖析以及实现了三种遍历形式，明天给大家分享另外一种二叉树的遍历形式档次遍历。 档次遍历所谓档次遍历，顾名思义就是指从二叉树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则依照从左到右的程序对节点一一拜访。在逐层遍历过程中，按从顶层到底层的秩序拜访树中元素，在同一层中，从左到右进行拜访。 以上图【图一】中的二叉树为例： 第一层：A第二层：B C第三层：D E F G那么其档次遍历的后果，就是：A B C D E F G非递归实现思路： 将根节点放入队列判断队列是否为空获取队列大小s，从队列头中出队s个元素，同时将s个元素的非空左右节点退出队列 根节点入队 上一层出队，其孩子节点入队如上图所示，根节点A出队，其子节点B 和 C 入队 第二层出队，其孩子节点入队第二层节点 B C出队，其子节点D E F G入队 第三层出队 队列中的节点D E F G出队，因为其没有子节点，遍历实现。 思考点：如何判断某一层是否齐全放入队列呢？那就是确保队列中的元素仅仅保留一层。下面可能了解起来有点艰难。在一开始的时候，根节点A入队，那么此时队列中的元素为第一层的所有节点(第一层仅有一个根节点A)。而后判断队列是否为空，获取队列元素个数s，从队列出弹出s个元素，同时将这些元素的子节点退出队列。 代码实现如下： struct TreeNode { TreeNode *left; TreeNode *right; int val;};void LevelOrder(TreeNode *root) { if (!root) { return; } std::queue<TreeNode*> q; q.push(root); while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; ++i) { auto t = q.front(); q.pop(); if (t->left) { q.push(t->left); } if (t->right) { q.push(t->right); } std::cout << t->val << std::endl; } }}递归实现递归的实现，从了解上，较非递归会简单一点。因为递归的个性，咱们会始终深度优先去解决左子结点，那么势必会穿梭不同的层，所以当要退出某个结点的时候，必须要晓得以后的深度，所以应用一个变量 level 来标记以后的深度，初始化带入0，示意根结点所在的深度。 ...

分割咱们：有道技术团队助手：ydtech01 / 邮箱：ydtech@rd.netease.com 前言本文属于系列文章《你真的理解二叉树吗》的第二局部——手撕算法篇。 如果你还没有看过第一局部《你真的理解二叉树吗（树形构造根底篇）》的话，强烈建议先看一下第一局部的内容，这样你在解题时会更加锦上添花。很多第一篇外面曾经讲过的内容，在这里将不再赘述。 一、二叉树根底刷题局部1.1 LeetCode 144 二叉树的前序遍历解题思路如果你有看过我上一篇文章《你真的理解二叉树吗（树形构造根底篇）》的话，应该曾经晓得了，咱们树的遍历天生就适宜应用递归实现。 此外，还讲了如何设计和实现一个递归函数，如果对着两点不太理解或没看过上一篇文章的同学，请先移步《你真的理解二叉树吗（树形构造根底篇）》补一下根底先，这里就不赘述了，间接讲思路吧： 首先，先设计一下咱们的递归函数 函数意义：前序遍历以 root 为根节点的二叉树边界条件：root 为空时无需遍历，间接返回 root递归过程：别离前序遍历左子树和前序遍历右子树代码演示/* * @lc app=leetcode.cn id=144 lang=typescript * * [144] 二叉树的前序遍历 */// @lc code=start/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */function preorderTraversal(root: TreeNode | null, arr: number[]=[]): number[] { // 判断边界条件 if(root) { // 因为是前序遍历，所以先将根节点退出数组 arr.push(root.val); // 递归遍历左子树和右子树 preorderTraversal(root.left, arr); preorderTraversal(root.right, arr); } return arr;};// @lc code=end以上是惯例的递归形式实现，咱们也能够应用迭代的形式实现： ...

分割咱们：有道技术团队助手：ydtech01 / 邮箱：mailto:ydtech@rd.netease.com 前言树形构造，尤其是二叉树，在咱们平时开发过程中应用频率比拟高，但之前对于树形构造没有一个比拟零碎全面的理解和认知，所以借此机会梳理一下。 本文属于《你真的理解二叉树吗》系列文章之一，次要介绍的是树形构造的根底，在看完这篇文章之后，如果想要更加熟练掌握二叉树的话，能够看另一篇《你真的理解二叉树吗（手撕算法篇）》（下周公布）。 一、树形构造根底相较于链表每个节点只能惟一指向下一个节点（此处说的链表是单向链表），树则是每个节点能够有若干个子节点，因而，咱们一个树形构造能够如下示意： interface TreeNode { data: any; nodes: TreeNode[]}1.1 树的度PS: 在图构造中，也有度的概念，分为出度和入度，如果把树看作是图的一部分的话，那么严格来说，树的度其实是出度。不过，在树形构造中，咱们通常把度这个概念作为形容以后树节点有几个子节点。 即每个节点领有几个孩子，因而，二叉树的度最大是 2，链表（能够看成只有一个孩子的树）的度最大是1。 定理： 在一个二叉树中，度为 0 的节点比度为 2 的节点多1。证实： 如果一个树有 n 个节点，那么，这棵树必定有 n-1 条边，也就是说，点的数量=边的数量+1(这个论断针对所有树形构造都实用，不仅仅是二叉树)如下图： 这个棵树有 7 个节点，节点与节点之间的连线，也就是边只有 6 条。 那么，咱们假如度为 0 的节点数量为 n0,度为 1的节点为数量 n1，度为 2 的节点数量为 n2，又因为是度为0的节点，阐明他的边的数量 N0=0，度为 1 的节点边的数量为 N1=n1 1，度为 2 的节点边的数量为 N2=n2 2，那么总共的节点数量为： #由上可知，边数量的表达式如下 N0=0; N1=1*n1; N2=2*n2; #由上可知，节点的数量=边的数量+1 n0 + n1 + n2 = N0 + N1 + N2 + 1; ...

A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically traversed or ordered. They are preorder, inorder and postorder. Let T be a binary tree with root r and subtrees T1,T2. In a preorder traversal of the vertices of T, we visit the root r followed by visiting the vertices of T1 in preorder, then the vertices of T2 in preorder. ...

前序遍历前序遍历是指，对于树中的任意节点来说，先打印这个节点，而后在打印它的左子树，最初打印它的右子树。 中序遍历中序遍历是指：对于树中的任意节点来说，先打印它的左子树，而后再打印它自身，最初打印它的右子树。 后序遍历后序遍历是指：对于树中的任意节点来说，先打印它的左子树，而后再打印它的右子树，最初打印这个节点自身。 前序遍历 自身节点->左子树->右节点preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)中序遍历 左子树->自身->右子树inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)后序遍历 左子树->右子树->节点自身postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r小结：树：是一种非线性数据结构。对于树，有几个比拟罕用的概念你须要把握，那就是：根节点、叶子节点、父节点、子节点、兄弟节点，还有高度，深度，层树。 二叉树：二叉树的每个节点最多有两个子节点，别离是左子节点和右子节点。

二叉树定义：每个节点最多有两个叉，也就是两个子节点，别离是左子节点和右子节点。不过二叉树不要求每个节点都有两个子二节点，有的节点只有左节点，有的节点只有右子节点。 满二叉树定义：叶子节点全副都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树 齐全二叉树定义：叶子节点都在最低下两层，最初一层的叶子节点都靠左排列，并且除了最初一层，其余层的节点个数都要达到最大。 如何存储一个二叉树两种办法：一种是基于指针或者援用的二叉链式存储法，一种是基于数组的顺序存储法。 链式存储法每个节点有三个字段， 一个字段存储数据，左右节点别离存储下一个节点的指针，只有找到了根节点，就能够通过左右子节点的指针，吧整棵树串联起来。 顺序存储法咱们把根节点存储在下标i=1的地位，那左子结点存储在下标为 2i的地位，下标为 2i + 1的存储就是右子节点。反过来，下标为 i/2的地位存储就是它的父节点

前言自己作为左程云的学生，现将课程上的morris遍历内容进行演绎整顿，java版本代码均为左老师课上代码，c++代码为自己间接改写，并均通过leetcode测试。什么是morris遍历morris遍历是利用二叉树自身闲暇进去的指针(n个节点的二叉树有n+1个指针闲暇)来作为辅助变量实现二叉树的遍历的一种办法。Morris遍历法能以O(1)的空间复杂度和O(n)的工夫复杂度实现二叉树的三种遍历,其中不应用栈或额定空间。 morris遍历流程1、咱们应用cur指针指向以后结点，mostRight指针指向cur左子树的最右结点，也即是cur的前驱结点2、如果以后结点没有左子树，咱们让cur往右走3、如果有左子树，那么找到其左子树的最右结点(原树中的最右结点，而不是批改过指针的最右结点，看到前面就分明了)，并应用mostRight保留。 3.1、如果mostRight的右指针为空，(阐明此时是第一次来到cur所指向结点)，让mostRight的右指针指向cur，而后让cur往左走。 3.2、如果mostRight的右指针不为空，(阐明此时是第二次来到cur所指向结点)，让mostRight的右指针从新置为null，而后cur往右走4、如果以后结点为空，遍历进行(回退过程合并到往右走了)。morris遍历图解： morris序在进行morris遍历的时候每次遍历都拜访该节点所取得的拜访程序就是morris序。在上述例子中的morris如下 1 2 4 2 5 1 3 6 3 7能够看到有的节点拜访了两次有的节点只拜访了一次，依据这个特点咱们能够推导出morris的前序，中序和后序序列，并且这里得记住一个特点就是，只有有左孩子的节点才会被拜访两次，没有左孩子的只会拜访一次。 morris序的代码实现java版本public static class Node { public int value; Node left; Node right; public Node(int data) { this.value = data; } }public static void morris(Node head) { if (head == null) { return; } Node cur = head; Node mostRight = null; while (cur != null) { mostRight = cur.left; if (mostRight != null) { // 有左树的状况下 // 找到cur左树上，实在的最右 while (mostRight.right != null && mostRight.right != cur) { mostRight = mostRight.right; } // 从while中进去，mostRight肯定是cur左树上的最右节点 // mostRight if (mostRight.right == null) {// 第一次来到cur结点 mostRight.right = cur; cur = cur.left; continue; } else { // mostRight.right != null -> mostRight.right == cur mostRight.right = null; } } // 没有左子树或者第二次来到cur结点 cur = cur.right; }}c++版本struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} };void morris(TreeNode* root){ if(!root) return; TreeNode* cur=root; TreeNode* mostRight; while(cur){ mostRight = cur->left; if(mostRight){ // 有左子树 while(mostRight->right&&mostRight->right!=cur){ // 只有有右孩子并且右孩子不是以后结点 mostRight = mostRight->right; } if(!mostRight->right){ // mostRight的右孩子为空，阐明是第一次拜访cur mostRight->right = cur; cur = cur->left; continue; }else{ // mostRight的右孩子为cur，阐明是第二次来到cur mostRight->right = nullptr; } } // 没有左子树或者第二次来到cur结点 cur = cur->right; }}morris先序遍历先序遍历就是在morris遍历的时候在第一次遍历以后结点的时候进行输入即可，这里间接给出代码，会发现改变的中央就2处 ...

上篇文章也提到了二叉树的劣势以及重要性，那么就让咱们来着手封装一个二叉树吧。咱们先来看看它有哪些常见的操作方法。 二叉搜寻树常见的操作insert(key):向树中插入一个新的键search(key)：在树中查找一个键，如果节点存在，则返回true；如果不存在，则返回falsepreOrderTraverse：通过先序遍历形式遍历所有节点inOrderTraverse:通过中序遍历形式遍历所有节点postorderTraverse:通过后序遍历形式遍历所有节点min：返回树中最小的值max:返回树中最大的值remove(key)：从树中移除某个键 insert（插入）办法封装代码前咱们先来捋一下insert的逻辑 要向树中插入一个新的节点或键要经验三个步骤。 1 第一步是验证插入操作树是否为一个空树。如果是,咱们要做的就是创立一个Node 类的实例并将它赋值给 root(根节点) 属性。2 如果树非空须要找到插入新节点的地位，寻找对应节点的办法：如下图，如果咱们须要在下图插入一个键为6的节点，那么就先拿6和11做比拟，发现6<11，就向左移，再而后6和7做比拟，6<7那么持续向下，和5做比拟，6>5，那就让6插入到5的右节点插入6的过程 封装代码首先每个节点都须要left(左指针),right(右指针)和key(键)组成，所以咱们须要先实现一个Node类 class CreateNode { constructor(key) { this.key = key; this.left = null; this.right = null; }}insert封装 // 插入新节点insert(key) { let newNode = new CreateNode(key); //判断是否为空树 if (!this.root) { this.root = newNode } else { let parent = null; let current = this.root; // isLeftChild来判断是左侧还是右侧 let isLeftChild = false; while (current) { parent = current if (key < current.key) { current = current.left; isLeftChild = true } else { current = current.right; isLeftChild = false; } } isLeftChild ? parent.left = newNode : parent.right = newNode }}先序遍历（preOrderTraverse）先序遍历是以优先于后辈节点的程序拜访每个节点的。先序遍历的一种利用是打印一个结构化的文档。 ...

144. 二叉树的前序遍历递归JAVA代码 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); return help(root, res); } public List<Integer> help (TreeNode root, List<Integer> list){ if (root != null) { list.add(root.val); help(root.left, list); help(root.right, list); } return list; } }迭代借用栈因为二叉树的前序遍历有往回走的过程，因而思考用栈构造。同时先拜访左孩子后拜访右孩子，因而入栈程序为先右孩子入栈后左孩子入栈。JAVA代码 ...

树的子结构1. 题目形容输出两棵二叉树A，B，判断B是不是A的子结构。（ps：咱们约定空树不是任意一个树的子结构） 2. 示例无 3. 解题思路波及树结构的题目，个别都应用递归办法 如果两棵二叉树 节点值不雷同：1-1： 递归遍历 A树左子树 1-2： 递归遍历 A 树右子树 如果两棵二叉树 节点值雷同：1-1：B树为空，则B是A的子树 1-2： 递归判断AB树节点值是否雷同 4. Java实现/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { boolean res = false; if (root1 != null && root2 != null){ if (root1.val == root2.val){ res = doseSubtree(root1, root2); } if (res == false){ res = HasSubtree(root1.left, root2); } if (res == false){ res = HasSubtree(root1.right, root2); } } return res; } private boolean doseSubtree(TreeNode root1,TreeNode root2){ if (root2 == null){ return true; } if (root1 == null){ return false; } if (root1.val != root2.val){ return false; } return doseSubtree(root1.left, root2.left) && doseSubtree(root1.right, root2.right); } }5. Python实现# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def HasSubtree(self, pRoot1, pRoot2): # write code here result = False if pRoot1 and pRoot2: #如果两颗树结点都不为空 if pRoot1.val == pRoot2.val:# 如果结点的值雷同的话 result = self.DoseSubtree(pRoot1, pRoot2) if not result: # 不雷同，则判断tree1 左子树结构 result = self.HasSubtree(pRoot1.left, pRoot2) if not result: result = self.HasSubtree(pRoot1.right, pRoot2) return result def DoseSubtree(self, pRoot1, pRoot2): if not pRoot2: #如果tree2 树为空的话，阐明就是子树 return True if not pRoot1: return False if pRoot1.val != pRoot2.val: return False # 持续判断1,2左子树和1,2右子树 return self.DoseSubtree(pRoot1.left, pRoot2.left) and self.DoseSubtree(pRoot1.right, pRoot2.right)如果您感觉本文有用，请点个“在看” ...

又是来自我的好朋友 EvilSay 的投稿，以下是原文： 1、基本定义二分搜索树的每个子节点最多有两个叶子节点二分搜索树的每个节点最多有一个根节点存储的元素必须具有可比较性二分搜索树每个子节点的值 大于其左子节的所有节点的值小于其右子节点的所有节点的值二分搜索树不一定是满的2、二分搜索树 Java 实现/** * @Author: EvilSay * @Date: 2019/8/6 19:00 */public class BSTMain <E extends Comparable<E>> { private class Node { public E e; private Node left, right; public Node(E e) { this.e = e; left = null; right = null; } } //根节点 private Node root; private int size; public BSTMain() { root = null; size = 0; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void add(E e){ root = add(this.root, e); } // 向node为根的二分搜索树中插入元素E,递归算法 // 返回插入新节点后二分搜索树的根 private Node add(Node node, E e){ if (node == null){ size ++; return new Node(e); } if (e.compareTo(node.e) < 0) node.left = add(node.left, e); else if (e.compareTo(node.e) > 0) node.right = add(node.right,e); return node; } // 看二分搜索树中是否包含元素e public boolean contains(E e){ return contains(root,e); } // 看以node为根的二分搜索树中是否包含元素e,递归算法 private boolean contains(Node node, E e){ if (node == null) return false; if (e.compareTo(node.e) == 0) return true; else if (e.compareTo(node.e) < 0) return contains(node.left, e); else return contains(node.right,e); } @Override public String toString() { StringBuilder res = new StringBuilder(); generateBSTSString(root,0,res); return res.toString(); } // 生成以node为根节点，深度为depth的描述二叉树的字符串 private void generateBSTSString(Node root, int depth, StringBuilder res) { if (root == null){ res.append(generateDepthString(depth) + "null\n"); return; } res.append(generateDepthString(depth) + root.e + "\n"); generateBSTSString(root.left, depth + 1 ,res); generateBSTSString(root.right, depth + 1, res); } private String generateDepthString(int depth) { StringBuilder res = new StringBuilder(); for (int i = 0; i < depth; i++) res.append("--"); return res.toString(); }}3、图解二分搜索树 ...

1. 前言想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手。非线性表（树、堆），可以说是前端程序员的内功，要知其然，知其所以然。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。 非线性表中的树、堆是干嘛用的 ？其数据结构是怎样的 ？ 希望大家带着这两个问题阅读下文。 2. 树 树的数据结构就像我们生活中的真实的树，只不过是倒过来的形状。 术语定义 节点：树中的每个元素称为节点，如 A、B、C、D、E、F、G、H、I、J。父节点：指向子节点的节点，如 A。子节点：被父节点指向的节点，如 A 的孩子 B、C、D。父子关系：相邻两节点的连线，称为父子关系，如 A 与 B，C 与 H，D 与 J。根节点：没有父节点的节点，如 A。叶子节点：没有子节点的节点，如 E、F、G、H、I、J。兄弟节点：具有相同父节点的多个节点称为兄弟节点，如 B、C、D。节点的高度：节点到叶子节点的最长路径所包含的边数。节点的深度：根节点到节点的路径所包含的边数。节点层数：节点的深度 +1（根节点的层数是 1 ）。树的高度：等于根节点的高度。森林： n 棵互不相交的树的集合。 高度是从下往上度量，比如一个人的身高 180cm ，起点就是从 0 开始的。深度是从上往下度量，比如泳池的深度 180cm ，起点也是从 0 开始的。高度和深度是带有度字的，都是从 0 开始计数的。而层数的计算，是和我们平时的楼层的计算是一样的，最底下那层是第 1 层，是从 1 开始计数的，所以根节点位于第 1 层，其他子节点依次加 1。 二叉树分类 二叉树每个节点最多只有 2 个子节点的树，这两个节点分别是左子节点和右子节点。如上图中的 1、 2、3。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。以此类推，自己想四叉树、八叉树的结构图。 满二叉树一种特殊的二叉树，除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。如上图中的 2。完全二叉树一种特殊的二叉树，叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。如上图的 3。完全二叉树与不是完全二叉树的区分比较难，所以对比下图看看。 堆之前的文章 栈内存与堆内存 、浅拷贝与深拷贝 中有说到：JavaScript 中的引用类型（如对象、数组、函数等）是保存在堆内存中的对象，值大小不固定，栈内存中存放的该对象的访问地址指向堆内存中的对象，JavaScript 不允许直接访问堆内存中的位置，因此操作对象时，实际操作对象的引用。 ...

题目描述请实现两个函数，分别用来序列化和反序列化二叉树 /*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { String Serialize(TreeNode root) { } TreeNode Deserialize(String str) { }}分析什么是二叉树的序列化和反序列化首先我们先来了解一下什么是二叉树的序列化和反序列化 二叉树的序列化：将二叉树保存在一个文件或者数组中，能够持久化的存储 二叉树的反序列化：从文件或者数组中取出数据，重构一颗二叉树 如何实现二叉树的序列化那么如何实现二叉树的序列化呢？我们知道二叉树有三种深度优先遍历方式：前序遍历、中序遍历、后序遍历 那么这三种遍历方式都可以实现将二叉树的序列化 基于前序遍历实现二叉树的序列化那么接下来我们选择基于前序遍历来实现二叉树的序列化 我们用‘$’表示空节点 String Serialize(TreeNode root) { StringBuffer stringBuffer = new StringBuffer(); SerializeSub(root, stringBuffer); return stringBuffer.toString(); } public void SerializeSub(TreeNode root, StringBuffer stringBuffer) { //当遇到空节点的时候，标记为$,不再继续递归遍历 if(root == null) { stringBuffer.append("$,"); }else { //按照前序遍历的顺序，依次添加节点的val到stringbuffer（root->left->right） stringBuffer.append(root.val + ","); SerializeSub(root.left, stringBuffer); SerializeSub(root.right, stringBuffer); } }实现二叉树的反序列化由于我们采用的是前序遍历序列化，那么同样反序列化也采用前序遍历反序列化 ...

题目描述从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。 思路该题和按照之字形打印二叉树差不多，需要每一层输出一行，也就是每一层需要输出一个list,那么需要两个队列进行合作，一个队列出队（保存上一层节点），一个队列入队（保存前一个队列的左右节点，即下一层节点），只不过该题和按照之字形二叉树打印的区别在于，之字形二叉树需要区分奇数层和偶数层，那么就需要两个队列保存左右节点的顺序不一样，上一个队列先保存左节点，再保存右节点；下一个队列先保存右节点，再保存左节点。 代码import java.util.ArrayList;import java.util.LinkedList;public class Print1 { public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> list = new ArrayList<>(); if(pRoot == null) return list; LinkedList<TreeNode> queue1 = new LinkedList<>(); LinkedList<TreeNode> queue2 = new LinkedList<>(); queue1.add(pRoot); while (!queue1.isEmpty() || !queue2.isEmpty()){ if(!queue1.isEmpty()){ ArrayList<Integer> subList = new ArrayList<>(); while (!queue1.isEmpty()){ TreeNode curNode = queue1.pollFirst(); subList.add(curNode.val); if(curNode.left != null){ queue2.add(curNode.left); } if(curNode.right != null){ queue2.add(curNode.right); } } list.add(subList); }else { ArrayList<Integer> subList1 = new ArrayList<>(); while (!queue2.isEmpty()){ TreeNode curNode = queue2.pollFirst(); subList1.add(curNode.val); if(curNode.left != null){ queue1.add(curNode.left); } if(curNode.right != null){ queue1.add(curNode.right); } } list.add(subList1); } } return list; }}

[TOC] 题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。 分析拿到这道题目，首先我们可以确定的是应该用层次遍历法遍历二叉树，所以在解题之前我们先来回顾一下基于广度优先的二叉树的遍历是怎样的 顺便贴上层次遍历法遍历二叉树的代码 public ArrayList<Integer> level(TreeNode root){ ArrayList<Integer> list = new ArrayList<>(); LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()){ TreeNode curNode = queue.pollFirst(); list.add(curNode.val); if(curNode.left != null) queue.add(curNode.left); if(curNode.right != null) queue.add(curNode.right); } return list; }错误示范接下来我们分析这道题目，本道题其实和基本的层次遍历很像，只是当层数为奇数的时候是从左到右遍历，当层数为偶数的时候是从右到左遍历（自顶向下计数），所以我们容易想到的办法是能不能用一个全局层数计数器，当奇数层的时候，我们先添加左节点再添加右节点；当为偶数层的时候，我们先添加右节点再添加左节点 (ps:这是错误方法) public ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot) { LinkedList<TreeNode> queue = new LinkedList<>(); ArrayList<ArrayList<Integer>> listResult = new ArrayList<>(); int count = 1; queue.add(pRoot); while (!queue.isEmpty()){ ArrayList<Integer> list = new ArrayList<>(); TreeNode curNode = queue.pollFirst(); list.add(curNode.val); count++; if(count %2 == 0){ if(curNode.right != null) queue.add(curNode.right); if(curNode.left != null) queue.add(curNode.left); }else { if(curNode.left != null) queue.add(curNode.left); if(curNode.right != null) queue.add(curNode.right); } listResult.add(list); } return listResult; }您的代码已保存答案错误:您提交的程序没有通过所有的测试用例case通过率为0.00%用例:{8,6,10,5,7,9,11}对应输出应该为:[[8],[10,6],[5,7,9,11]]你的输出为:[[8],[10],[6],[9],[11],[7],[5]]通过用例测试我们发现了用一个队列无法实现，count并不能记录层数的奇偶性 ...

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 /*public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; }}*/思路要求中序遍历的下一个节点，那么首先需要对节点进行分类，哪些节点的下一个节点是是父节点，哪些节点的下一个节点与子节点有关上图将节点分成了三类，实际上我们可以根据红色箭头的指向，分成两类，紫色和橙色的节点为一类，蓝色的为一类 紫色和橙色节点：共同点都是本身没有右孩子。 如果本身又是父节点的左孩子，那么下一个节点就是父节点如果本身不是父节点的左孩子，那么继续寻找，直到找到一个祖先是某个节点a的左孩子，那么下一个节点就是节点a蓝色节点：该节点有右孩子 该节点的右孩子没有左孩子：下一个节点就是该节点的右孩子该节点的右孩子还有左孩子：下一个节点就是该节点的右孩子的左孩子，如果左孩子还有左孩子，就继续遍历，直到遇到最后一个左孩子就是下一个节点感觉文字描述有点啰嗦，下面直接看代码，总而言之就是将节点分成了两大类（根据有没有右孩子），然后每个大类又分成了两个小类 public TreeLinkNode GetNext(TreeLinkNode pNode) { if(pNode==null) return null; if(pNode.right!=null){ //如果有右子树，则找右子树的最左节点 pNode = pNode.right; while(pNode.left!=null) pNode = pNode.left; return pNode; } while(pNode.next!=null){ //没右子树，则找第一个当前节点是父节点左孩子的节点 if(pNode.next.left==pNode) return pNode.next; pNode = pNode.next; } return null; //退到了根节点仍没找到，则返回null }总结本题的关键点在于画出中序遍历的图，发现规律，将节点进行分类欢迎关注：小秋的博客

1. 前言算法为王。排序算法博大精深，前辈们用了数年甚至一辈子的心血研究出来的算法，更值得我们学习与推敲。因为之后要讲有内容和算法，其代码的实现都要用到递归，所以，搞懂递归非常重要。 1. 定义方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。简单来说就是：自己调用自己。 现实例子：周末你带着女朋友去电影院看电影，女朋友问你，咱们现在坐在第几排啊 ？电影院里面太黑了，看不清，没法数，现在你怎么办 ？ 于是你就问前面一排的人他是第几排，你想只要在他的数字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也问他前面的人。就这样一排一排往前问，直到问到第一排的人，说我在第一排，然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排，于是你就知道答案了。 基本上，所有的递归问题都可以用递推公式来表示，比如: f(n) = f(n-1) + 1; // 其中，f(1) = 1 f(n) 表示你想知道自己在哪一排，f(n-1) 表示前面一排所在的排数，f(1) = 1 表示第一排的人知道自己在第一排。 有了这个递推公式，我们就可以很轻松地将它改为递归代码，如下： function f(n) { if (n == 1) return 1; return f(n-1) + 1;}2. 为什么使用递归 ？递归的优缺点 ？优点：代码的表达力很强，写起来简洁。缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。3. 什么样的问题可以用递归解决呢 ？一个问题只要同时满足以下 3 个条件，就可以用递归来解决。 问题的解可以分解为几个子问题的解。何为子问题 ？就是数据规模更小的问题。比如，前面讲的电影院的例子，你要知道，自己在哪一排的问题，可以分解为前一排的人在哪一排这样一个子问题。 问题与子问题，除了数据规模不同，求解思路完全一样比如电影院那个例子，你求解自己在哪一排的思路，和前面一排人求解自己在哪一排的思路，是一模一样的。 存在递归终止条件比如电影院的例子，第一排的人不需要再继续询问任何人，就知道自己在哪一排，也就是 f(1) = 1，这就是递归的终止条件。 4. 递归常见问题及解决方案警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。5. 如何实现递归 ？1. 递归代码编写 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。 2. 递归代码理解 对于递归代码，若试图想清楚整个递和归的过程，实际上是进入了一个思维误区。 那该如何理解递归代码呢 ？ 如果一个问题 A 可以分解为若干个子问题 B、C、D，你可以假设子问题 B、C、D 已经解决。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。因此，理解递归代码，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。 ...

定义树的节点 typedef struct TreeNode { int data; struct TreeNode *leftChild; struct TreeNode *RightChild; } TreeNode;创建树 /** * 1 * / \ * 2 3 * /\ / * 4 5 6 */ TreeNode *root = malloc(sizeof(TreeNode)); root->data = 1; TreeNode *node1 = malloc(sizeof(TreeNode)); node1->data = 2; TreeNode *node2 = malloc(sizeof(TreeNode)); node2->data = 3; TreeNode *node3 = malloc(sizeof(TreeNode)); node3->data = 4; node3->leftChild = NULL; node3->RightChild = NULL; TreeNode *node4 = malloc(sizeof(TreeNode)); node4->data = 5; node4->leftChild = NULL; node4->RightChild = NULL; TreeNode *node5 = malloc(sizeof(TreeNode)); node5->data = 6; node5->leftChild = NULL; node5->RightChild = NULL; root->leftChild = node1; root->RightChild = node2; node1->leftChild = node3; node1->RightChild = node4; node2->leftChild = node5; node2->RightChild= NULL;前序遍历 // 前序遍历 根->左->右 void preorderTraverse(TreeNode *tree, NSMutableArray *arrayM) { if(tree == NULL) {return;} [arrayM addObject:@(tree->data)];// 记录节点 preorderTraverse(tree->leftChild, arrayM); preorderTraverse(tree->RightChild, arrayM); }中序遍历//中序遍历 左->根->右 void midTraverse(TreeNode *tree, NSMutableArray *arrayM) { if(tree == NULL) {return;} midTraverse(tree->leftChild, arrayM); [arrayM addObject:@(tree->data)];// 记录节点 midTraverse(tree->RightChild, arrayM); }后序遍历 //后序遍历 左->右->根 void postorderTraversal(TreeNode *tree, NSMutableArray *arrayM) { if(tree == NULL) {return;} postorderTraversal(tree->leftChild, arrayM); postorderTraversal(tree->RightChild, arrayM); [arrayM addObject:@(tree->data)];// 记录节点 }输出遍历后的节点 NSMutableArray *arrayM = [NSMutableArray array]; preorderTraverse(root, arrayM); NSLog(@"%@",arrayM);// 124536 NSMutableArray *arrayM1 = [NSMutableArray array]; midTraverse(root, arrayM1); NSLog(@"%@",arrayM1);//425163 NSMutableArray *arrayM2 = [NSMutableArray array]; postorderTraversal(root, arrayM2); NSLog(@"%@",arrayM2);// 452631

定义Wikipedia - AVL树 在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 {displaystyle O(log {n})} O(log{n})。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。理论实现AVL树的要点为：每次新增/删除节点后判断平衡性然后通过调整使整棵树重新平衡 判断平衡性：每次新增/删除节点后，刷新受到影响的节点的高度，即可通过任一节点的左右子树高度差判断其平衡性 调整：通过对部分节点的父子关系的改变使树重新平衡 实现基本结构public class Tree<T extends Comparable<T>> { private static final int MAX_HEIGHT_DIFFERENCE = 1; private Node<T> root; class Node<KT> { KT key; Node<KT> left; Node<KT> right; int height = 1; public Node(KT key, Node<KT> left, Node<KT> right) { this.key = key; this.left = left; this.right = right; } }}插入（insert）四种不平衡范型对于任意一次插入所造成的不平衡，都可以简化为下述四种范型之一： ...

平衡：树的左右子树的高度差距在一个可控的范围内 B-TREE 多路搜索树AVL 平衡二叉树: 空树或它的左右两个子树的高度差的绝对值不超过1，左右两个子树都是一颗平衡二叉树。RB-TREE 红黑树: 红黑树属于平衡二叉树，但不是严格的平衡二叉树，相对接近平衡的二叉树， 最大深度<=最小深度的两倍(即没有一条路径比其他路径长出两倍)BST 二叉搜索树(Binary Search Tree):BBST 平衡二叉排序树(Balance Binary Sort Tree)红黑树概念: 红黑树特点: 红黑树应用场景: TreeMap 基于红黑树实现的排序Map，默认按key(实现comparable接口)来比较排序。 TreeMap的增删查改以及统计操作的时间复杂度都为O(logn)TreeSetJDK1.8中 HashMap每个数组节点挂的元素个数超过8 ConcurrentHashMap每个数组节点挂的元素个数超过8红黑树与AVL树对比: 红黑树的查询性能略逊色于AVL树 红黑树放弃了追求完全平衡，追求大致平衡， 红黑树的高度相对更高，因此红黑树的插入和删除性能比AVL效率高

前言Weekly Contest 132的 节点与其祖先之间的最大差值：给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）示例：输入：[8,3,10,1,6,null,14,null,null,4,7,13]输出：7解释： 我们有大量的节点与其祖先的差值，其中一些如下：|8 - 3| = 5|3 - 7| = 4|8 - 1| = 7|10 - 13| = 3在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。提示：树中的节点数在 2 到 5000 之间。每个节点的值介于 0 到 100000 之间。解题思路本题需要将问题分解一下，首先先实现根节点与每个节点的差值的最大值的算法，然后只需要遍历每个子树即可。实现代码 /** * 5030. 节点与其祖先之间的最大差值 * @param root * @return / public int maxAncestorDiff(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int max=0; while(!queue.isEmpty()){//层序遍历 TreeNode node=queue.poll(); max=Math.max(max,getMaxDiffByRoot(node)); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } return max; } /* * 获取某个根节点下所有节点与根节点的差值的最大值 * 这里选择使用层序遍历 * @param root * @return */ private int getMaxDiffByRoot(TreeNode root){ Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); //根节点的值，用于比较 int rootValue=root.val; //最大差值 int max=0; while(!queue.isEmpty()){//层序遍历每个节点 TreeNode node=queue.poll(); // 获取最大值 max=Math.max(max,Math.abs(node.val-rootValue)); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } return max; } ...

为什么会写这篇文章学习的时间越来越长总会忘掉一些东西，就比如向量，矩阵，二叉树，邻接表，太多太多东西，不用就都给忘了，今天看了这样一道面试题：总结下来就是根据二叉树的前中序遍历，然后写出后序遍历，清晰的记得当时学习二叉树的时候做这种题是很快的，可是我还真就卡住了，不是说需要做一会儿，是做不出来，看过好多遍使用程序实现DFS(深度优先)BFS(广度优先)的例子，可是让我用笔推断，我还真就脑子瓦特了，所以也记录一下，顺便帮一下也忘记了手工推断的你们回忆一下，你们一定都比我优秀，perfect。题目：前序遍历A D C E F G H B中序遍历C D F E G H A B后序遍历？这些遍历就是根据遍历根节点的顺序而定义的，前序遍历就是优先遍历根节点然后遍历左右子节点，当然左右子节点也是根据这个原则遍历的，那么中后序遍历也一样。那么我们应该怎么去做呢？其实就是根据前中遍历的结果推断出这颗树。。。第一步根据前序遍历原则找出根节点：A 因为优先遍历根节点根据根节点A和中序遍历划分前中序遍历的左右子树，以中左表示，前序遍历的左右子树，以前左表示：中左：C D F E G H中右：B前左：D C E F G H前右：B第二步根据上面的中左，前左继续划分根节点：D 由于右子树就一个节点，所以就结束了根据根节点D和中序遍历划分前中序遍历的左右子树中左：C中右：F E G H前左：C前右：E F G H第三步根据上面的中右，前右继续划分根节点：E 由于左子树就一个节点，所以就结束了根据根节点E和中序遍历划分前中序遍历的左右子树中左：F中右：G H前左：F前右：G H第四步根据上面的中右，前右继续划分根节点：G 由于左子树就一个节点，所以就结束了根据根节点G和中序遍历划分前中序遍历的左右子树中左：中右：H前左：前右：H终于构建出来这颗树了，接下来根据后序遍历原则去写：后序遍历结果亮相：C F H G E D B A只有多学习才能变得更强，还是那句话:坚持一件事，对自己。

题目给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:给定的有序链表： [-10, -3, 0, 5, 9],一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5题解这道题和上一道类似,改动是把数组改成了链表。链表求中间节点的经典方法是快慢指针,慢指针每次走一步,快指针每次都走两步，这样快指针走到链表结尾的时候，慢指针就指向中间节点。这样就可以把问题转化为递归的子问题进行求解。class Solution { public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } return helper(head, null); } public TreeNode helper(ListNode head, ListNode tail) { if (head == null || head == tail) { return null; } ListNode slow = head; ListNode fast = head; while (fast.next != tail && fast.next.next != tail) { fast = fast.next.next; slow = slow.next; } TreeNode current = new TreeNode(slow.val); current.left = helper(head, slow); current.right = helper(slow.next, tail); return current; } }这道题目还有一个比较巧妙的办法是利用BST中序遍历是升序的性质，去求解，具体看代码注释。class Solution { private ListNode node; public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } int size = 0; ListNode runner = head; node = head; while (runner != null) { runner = runner.next; size++; } // 先计算有几个节点 return inorderHelper(0, size - 1); } public TreeNode inorderHelper(int start, int end) { if (start > end) { return null; } // 划分左右子树 int mid = start + (end - start) / 2; TreeNode left = inorderHelper(start, mid - 1); // 中序遍历 TreeNode treenode = new TreeNode(node.val); treenode.left = left; node = node.next; TreeNode right = inorderHelper(mid + 1, end); treenode.right = right; return treenode; }}最关键的一个步骤是node = node.next 这步的意思是基于：在BST中任意子树，它的中序遍历的结果如果存在一个链表中，一定是一个升序的，可以一一对应上，所以中序遍历完（这里是构建完）一个节点链表+1。热门阅读【Leetcode】108. 将有序数组转换为二叉搜索树【Leetcode】107. 二叉树的层次遍历 II【Leetcode】105. 从前序与中序遍历序列构造二叉树【Leetcode】106. 从中序与后序遍历序列构造二叉树手撕代码QQ群：805423079， 群密码：1024 ...

题目给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）例如：给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回其自底向上的层次遍历为：[ [15,7], [9,20], [3]]题解利用层次遍历,层次遍历的时候进入下一层的时候记录一下当前队列中有几个元素。class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> levelVal = new LinkedList<>(); while (size > 0) { TreeNode current = queue.poll(); if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } levelVal.add(current.val); size–; } res.add(0, levelVal); } return res; }}用递归去做。用递归去做的关键在于需要把层数也带上。class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } helper(root, res, 0); return res; } public void helper(TreeNode root, List<List<Integer>> res, int depth) { if (root == null) { return; } if (depth == res.size()) { res.add(0, new LinkedList<>()); } List<Integer> current = res.get(res.size() - depth - 1); helper(root.left, res, depth + 1); helper(root.right, res, depth + 1); current.add(root.val); }}热门阅读技术文章汇总【Leetcode】103. 二叉树的锯齿形层次遍历【Leetcode】102. 二叉树的层次遍历【Leetcode】101. 对称二叉树【Leetcode】100. 相同的树【Leetcode】98. 验证二叉搜索树手撕代码QQ群：805423079， 群密码：1024 ...

章节目录T*-tree的介绍T*-tree节点与Ｃ语言实现T*-tree的插入、删除、查找与旋转实现简单的key-value内存数据库参考文献T-tree和T*-tree极为相似，他们的不同主要是T×-tree的节点结构比T-tree多了一个指向successor的指针位,指向successor的指针的存在是的树的寻找和遍历的时间复杂度.注：本文中关于ttree的head file ：ttree.h和ttree_defs.h来源于Dan Kruchinin <dkruchinin@acm.org>，Github：dkruchinin/libttreeT*-tree的介绍在计算机科学中，T-tree是一种二叉树，它有一个左子树和一个右子树，由主存储器数据库使用，例如Datablitz，EXtremeDB，MySQL Cluster，Oracle TimesTen和MobileLite。T树是一种平衡的索引树数据结构，针对索引和实际数据都完全保存在内存中的情况进行了优化，就像B树是针对面向块的辅助存储设备（如硬盘）上的存储而优化的索引结构。 T树寻求获得内存树结构（如AVL树）的性能优势，同时避免它们常见的大存储空间开销。T树不保留索引树节点本身内的索引数据字段的副本。 相反，它们利用了这样的事实：实际数据总是与索引一起在主存储器中，因此它们只包含指向实际数据字段的指针。虽然T树以前被广泛用于主存数据库，但最近的研究表明它们在现代硬件上的表现并不比B树好。主要原因是现代的内存和硬盘的速度差异越来越大了，内存访问速度比硬盘访问速度快，并且CPU的核心缓存容量也越来越大。T*-tree的节点结构与C语言实现T树节点通常由指向父节点，左右子节点，有序数据指针数组和一些额外控制数据的指针组成。 具有两个子树的节点称为内部节点（internal nodes），没有子树的节点称为叶子节点（leaf nodes），而仅具有一个子树的节点称为半叶节点（half-leaf nodes）。 如果值在节点的当前最小值和最大值之间，则该节点称为（bounding node）。对于每个内部节点,它的左子树中会有一个叶子节点或半叶子节点中有一个predecessor（称为最大下限-GLB(Greatest Lower Bound)），还在右子树中包含其最大数据值的后继者（LUB-lower upper bound）的节点(包含GLB或LUP的节点或许距离参照内部节点的距离很远,但也有可能恰好相邻。正因为T-tree的每个节点是有序的，并且不同节点之间保证左子树的数据都比节点数据的最小值小，右子树的数据都比节点数据的最大值大，因此B-tree最左边的节点中最左边的数据是整棵树最小的数据，最右边的节点中的最大值是整棵树最大的数据。叶子和半叶节点中的数据元素量在1~最大元素量之间，内部节点将其占用保持在预定义的最小元素量和最大元素数之间。如图：T-tree，T-treenode的插入、删除、旋转和查找代码来自于:Github:dkruchinin/libttree typedef struct ttree_node { struct ttree_node *parent; /< Pointer to node’s parent */ struct ttree_node *successor; /< Pointer to node’s soccussor */ union { struct ttree_node *sides[2]; struct { struct ttree_node *left; /< Pointer to node’s left child */ struct ttree_node *right; /< Pointer to node’s right child */ }; }; union { uint32_t pad; struct { signed min_idx :12; /< Index of minimum item in node’s array */ signed max_idx :12; /< Index of maximum item in node’s array */ signed bfc :4; /< Node’s balance factor */ unsigned node_side :4; /< Node’s side(TNODE_LEFT, TNODE_RIGHT or TNODE_ROOT) / }; };T-tree的插入、删除、查找与旋转插入int ttree_insert(Ttree *ttree, void item){ TtreeCursor cursor; / * If the tree already contains the same key item has and * tree’s wasn’t allowed to hold duplicate keys, signal an error. */ if (ttree_lookup(ttree, ttree_item2key(ttree, item), &cursor) && ttree->keys_are_unique) { return -1; } ttree_insert_at_cursor(&cursor, item); return 0;}void ttree_insert_at_cursor(TtreeCursor *cursor, void *item){ Ttree *ttree = cursor->ttree; TtreeNode *at_node, *n; TtreeCursor tmp_cursor; void key; TTREE_ASSERT(cursor->ttree != NULL); //TTREE_ASSERT(cursor->state == CURSOR_PENDING); key = ttree_item2key(ttree, item); n = at_node = cursor->tnode; if (!ttree->root) { / The root node has to be created. / at_node = allocate_ttree_node(ttree); at_node->keys[first_tnode_idx(ttree)] = key; at_node->min_idx = at_node->max_idx = first_tnode_idx(ttree); ttree->root = at_node; tnode_set_side(at_node, TNODE_ROOT); ttree_cursor_open_on_node(cursor, ttree, at_node, TNODE_SEEK_START); return; } if (cursor->side == TNODE_BOUND) { if (tnode_is_full(ttree, n)) { / * If node is full its max item should be removed and * new key should be inserted into it. Removed key becomes * new insert value that should be put in successor node. */ void tmp = n->keys[n->max_idx–]; increase_tnode_window(ttree, n, &cursor->idx); n->keys[cursor->idx] = key; key = tmp; ttree_cursor_copy(&tmp_cursor, cursor); cursor = &tmp_cursor; / * If current node hasn’t successor and right child * New node have to be created. It’ll become the right child * of the current node. / if (!n->successor || !n->right) { cursor->side = TNODE_RIGHT; cursor->idx = first_tnode_idx(ttree); goto create_new_node; } at_node = n->successor; / * If successor hasn’t any free rooms, new value is inserted * into newly created node that becomes left child of the current * node’s successor. / if (tnode_is_full(ttree, at_node)) { cursor->side = TNODE_LEFT; cursor->idx = first_tnode_idx(ttree); goto create_new_node; } / * If we’re here, then successor has free rooms and key * will be inserted to one of them. */ cursor->idx = at_node->min_idx; cursor->tnode = at_node; } increase_tnode_window(ttree, at_node, &cursor->idx); at_node->keys[cursor->idx] = key; cursor->state = CURSOR_OPENED; return; }create_new_node: n = allocate_ttree_node(ttree); n->keys[cursor->idx] = key; n->min_idx = n->max_idx = cursor->idx; n->parent = at_node; at_node->sides[cursor->side] = n; tnode_set_side(n, cursor->side); cursor->tnode = n; cursor->state = CURSOR_OPENED; fixup_after_insertion(ttree, n, cursor);}删除void *ttree_delete(Ttree *ttree, void *key){ TtreeCursor cursor; void *ret; ret = ttree_lookup(ttree, key, &cursor); if (!ret) { return ret; } ttree_delete_at_cursor(&cursor); return ret;}void *ttree_delete_at_cursor(TtreeCursor *cursor){ Ttree *ttree = cursor->ttree; TtreeNode *tnode, n; void ret; TTREE_ASSERT(cursor->ttree != NULL); TTREE_ASSERT(cursor->state == CURSOR_OPENED); tnode = cursor->tnode; ret = ttree_key2item(ttree, tnode->keys[cursor->idx]); decrease_tnode_window(ttree, tnode, &cursor->idx); cursor->state = CURSOR_CLOSED; if (UNLIKELY(cursor->idx > tnode->max_idx)) { cursor->idx = tnode->max_idx; } / * If after a key was removed, T-tree node contains more than * minimum allowed number of items, the proccess is completed. / if (tnode_num_keys(tnode) > min_tnode_entries(ttree)) { return ret; } if (is_internal_node(tnode)) { int idx; / * If it is an internal node, we have to recover number * of items from it by moving one item from its successor. / n = tnode->successor; idx = tnode->max_idx + 1; increase_tnode_window(ttree, tnode, &idx); tnode->keys[idx] = n->keys[n->min_idx++]; if (UNLIKELY(cursor->idx > tnode->max_idx)) { cursor->idx = tnode->max_idx; } if (!tnode_is_empty(n) && is_leaf_node(n)) { return ret; } / * If we’re here, then successor is either a half-leaf * or an empty leaf. / tnode = n; } if (!is_leaf_node(tnode)) { int items, diff; n = tnode->left ? tnode->left : tnode->right; items = tnode_num_keys(n); / * If half-leaf can not be merged with a leaf, * the proccess is completed. / if (items > (ttree->keys_per_tnode - tnode_num_keys(tnode))) { return ret; } if (tnode_get_side(n) == TNODE_RIGHT) { / * Merge current node with its right leaf. Items from the leaf * are placed after the maximum item in a node. */ diff = (ttree->keys_per_tnode - tnode->max_idx - items) - 1; if (diff < 0) { memcpy(tnode->keys + tnode->min_idx + diff, tnode->keys + tnode->min_idx, sizeof(void *) * tnode_num_keys(tnode)); tnode->min_idx += diff; tnode->max_idx += diff; if (cursor->tnode == tnode) { cursor->idx += diff; } } memcpy(tnode->keys + tnode->max_idx + 1, n->keys + n->min_idx, sizeof(void ) * items); tnode->max_idx += items; } else { / * Merge current node with its left leaf. Items the leaf * are placed before the minimum item in a node. */ diff = tnode->min_idx - items; if (diff < 0) { register int i; for (i = tnode->max_idx; i >= tnode->min_idx; i–) { tnode->keys[i - diff] = tnode->keys[i]; } tnode->min_idx -= diff; tnode->max_idx -= diff; if (cursor->tnode == tnode) { cursor->idx -= diff; } } memcpy(tnode->keys + tnode->min_idx - items, n->keys + n->min_idx, sizeof(void ) * items); tnode->min_idx -= items; } n->min_idx = 1; n->max_idx = 0; tnode = n; } if (!tnode_is_empty(tnode)) { return ret; } / if we’re here, then current node will be removed from the tree. */ n = tnode->parent; if (!n) { ttree->root = NULL; free(tnode); return ret; } n->sides[tnode_get_side(tnode)] = NULL; fixup_after_deletion(ttree, tnode, NULL); free(tnode); return ret;}查找void *ttree_lookup(Ttree *ttree, void *key, TtreeCursor *cursor){ TtreeNode *n, *marked_tn, *target; int side = TNODE_BOUND, cmp_res, idx; void item = NULL; enum ttree_cursor_state st = CURSOR_PENDING; / * Classical T-tree search algorithm is O(log(2N/M) + log(M - 2)) * Where N is total number of items in the tree and M is a number of * items per node. In worst case each node on the path requires 2 * comparison(with its min and max items) plus binary search in the last * node(bound node) excluding its first and last items. * * Here is used another approach that was suggested in * “Tobin J. Lehman , Michael J. Carey, A Study of Index Structures for * Main Memory Database Management Systems”. * It reduces O(log(2N/M) + log(M - 2)) to true O(log(N)). * This algorithm compares the search * key only with minimum item in each node. If search key is greater, * current node is marked for future consideration. / target = n = ttree->root; marked_tn = NULL; idx = first_tnode_idx(ttree); if (!n) { goto out; } while (n) { target = n; cmp_res = ttree->cmp_func(key, tnode_key_min(n)); if (cmp_res < 0) side = TNODE_LEFT; else if (cmp_res > 0) { marked_tn = n; / mark current node for future consideration. / side = TNODE_RIGHT; } else { / ok, key is found, search is completed. / side = TNODE_BOUND; idx = n->min_idx; item = ttree_key2item(ttree, tnode_key_min(n)); st = CURSOR_OPENED; goto out; } n = n->sides[side]; } if (marked_tn) { int c = ttree->cmp_func(key, tnode_key_max(marked_tn)); if (c <= 0) { side = TNODE_BOUND; target = marked_tn; if (!c) { item = ttree_key2item(ttree, tnode_key_max(target)); idx = target->max_idx; st = CURSOR_OPENED; } else { / make internal binary search / struct tnode_lookup tnl; tnl.key = key; tnl.low_bound = target->min_idx + 1; tnl.high_bound = target->max_idx - 1; item = lookup_inside_tnode(ttree, target, &tnl, &idx); st = (item != NULL) ? CURSOR_OPENED : CURSOR_PENDING; } goto out; } } / * If we’re here, item wasn’t found. So the only thing * needs to be done is to determine the position where search key * may be placed to. If target node is not empty, key may be placed * to its min or max positions. */ if (!tnode_is_full(ttree, target)) { side = TNODE_BOUND; idx = ((marked_tn != target) || (cmp_res < 0)) ? target->min_idx : (target->max_idx + 1); st = CURSOR_PENDING; }out: if (cursor) { ttree_cursor_open_on_node(cursor, ttree, target, TNODE_SEEK_START); cursor->side = side; cursor->idx = idx; cursor->state = st; } return item;}旋转static void __rotate_single(TtreeNode **target, int side){ TtreeNode *p, *s; int opside = opposite_side(side); p = *target; TTREE_ASSERT(p != NULL); s = p->sides[side]; TTREE_ASSERT(s != NULL); tnode_set_side(s, tnode_get_side(p)); p->sides[side] = s->sides[opside]; s->sides[opside] = p; tnode_set_side(p, opside); s->parent = p->parent; p->parent = s; if (p->sides[side]) { p->sides[side]->parent = p; tnode_set_side(p->sides[side], side); } if (s->parent) { if (s->parent->sides[side] == p) s->parent->sides[side] = s; else s->parent->sides[opside] = s; } target = s;}/ * There are two cases of single rotation possible: * 1) Right rotation (side = TNODE_LEFT) * [P] [L] * / \ / \ * [L] x1 => x2 [P] * / \ / \ * x2 x3 x3 x1 * * 2) Left rotation (side = TNODE_RIHGT) * [P] [R] * / \ / \ * x1 [R] => [P] x2 * / \ / \ * x3 x2 x1 x3 */static void rotate_single(TtreeNode **target, int side){ TtreeNode *n; __rotate_single(target, side); n = (target)->sides[opposite_side(side)]; / * Recalculate balance factors of nodes after rotation. * Let X was a root node of rotated subtree and Y was its * child. After single rotation Y is new root of subtree and X is its child. * Y node may become either balanced or overweighted to the * same side it was but 1 level less. * X node scales at 1 level down and possibly it has new child, so * its balance should be recalculated too. If it still internal node and * its new parent was not overwaighted to the opposite to X side, * X is overweighted to the opposite to its new parent side, * otherwise it’s balanced. If X is either half-leaf or leaf, * balance racalculation is obvious. */ if (is_internal_node(n)) { n->bfc = (n->parent->bfc != side2bfc(side)) ? side2bfc(side) : 0; } else { n->bfc = !!(n->right) - !!(n->left); } (*target)->bfc += side2bfc(opposite_side(side)); TTREE_ASSERT((abs(n->bfc < 2) && (abs((target)->bfc) < 2)));}/ * There are two possible cases of double rotation: * 1) Left-right rotation: (side == TNODE_LEFT) * [P] [r] * / \ / \ * [L] x1 [L] [P] * / \ => / \ / \ * x2 [r] x2 x4 x3 x1 * / \ * x4 x3 * * 2) Right-left rotation: (side == TNODE_RIGHT) * [P] [l] * / \ / \ * x1 [R] [P] [R] * / \ => / \ / \ * [l] x2 x1 x3 x4 x2 * / \ * x3 x4 */static void rotate_double(TtreeNode **target, int side){ int opside = opposite_side(side); TtreeNode *n = (target)->sides[side]; __rotate_single(&n, opside); / * Balance recalculation is very similar to recalculation after * simple single rotation. */ if (is_internal_node(n->sides[side])) { n->sides[side]->bfc = (n->bfc == side2bfc(opside)) ? side2bfc(side) : 0; } else { n->sides[side]->bfc = !!(n->sides[side]->right) - !!(n->sides[side]->left); } TTREE_ASSERT(abs(n->sides[side]->bfc) < 2); n = n->parent; __rotate_single(target, side); if (is_internal_node(n)) { n->bfc = ((target)->bfc == side2bfc(side)) ? side2bfc(opside) : 0; } else { n->bfc = !!(n->right) - !!(n->left); } / * new root node of subtree is always ideally balanced * after double rotation. */ TTREE_ASSERT(abs(n->bfc) < 2); (*target)->bfc = 0;}static void rebalance(Ttree *ttree, TtreeNode **node, TtreeCursor *cursor){ int lh = left_heavy(*node); int sum = abs((*node)->bfc + (node)->sides[opposite_side(lh)]->bfc); if (sum >= 2) { rotate_single(node, opposite_side(lh)); goto out; } rotate_double(node, opposite_side(lh)); / * T-tree rotation rules difference from AVL rules in only one aspect. * After double rotation is done and a leaf became a new root node of * subtree and both its left and right childs are half-leafs. * If the new root node contains only one item, N - 1 items should * be moved into it from one of its childs. * (N is a number of items in selected child node). */ if ((tnode_num_keys(*node) == 1) && is_half_leaf((*node)->left) && is_half_leaf((*node)->right)) { TtreeNode n; int offs, nkeys; / * If right child contains more items than left, they will be moved * from the right child. Otherwise from the left one. */ if (tnode_num_keys((*node)->right) >= tnode_num_keys((node)->left)) { / * Right child was selected. So first N - 1 items will be copied * and inserted after parent’s first item. */ n = (*node)->right; nkeys = tnode_num_keys(n); (*node)->keys[0] = (*node)->keys[(*node)->min_idx]; offs = 1; (*node)->min_idx = 0; (*node)->max_idx = nkeys - 1; if (!cursor) { goto no_cursor; } else if (cursor->tnode == n) { if (cursor->idx < n->max_idx) { cursor->tnode = *node; cursor->idx = (node)->min_idx + (cursor->idx - n->min_idx + 1); } else { cursor->idx = first_tnode_idx(ttree); } } } else { / * Left child was selected. So its N - 1 items * (starting after the min one) * will be copied and inserted before parent’s single item. / n = (node)->left; nkeys = tnode_num_keys(n); (node)->keys[ttree->keys_per_tnode - 1] = (node)->keys[(node)->min_idx]; (node)->min_idx = offs = ttree->keys_per_tnode - nkeys; (node)->max_idx = ttree->keys_per_tnode - 1; if (!cursor) { goto no_cursor; } else if (cursor->tnode == n) { if (cursor->idx > n->min_idx) { cursor->tnode = node; cursor->idx = (node)->min_idx + (cursor->idx - n->min_idx); } else { cursor->idx = first_tnode_idx(ttree); } } n->max_idx = n->min_idx++; }no_cursor: memcpy((node)->keys + offs, n->keys + n->min_idx, sizeof(void ) * (nkeys - 1)); n->keys[first_tnode_idx(ttree)] = n->keys[n->max_idx]; n->min_idx = n->max_idx = first_tnode_idx(ttree); }out: if (ttree->root->parent) { ttree->root = node; }}实现简单的key-value内存数据库实现简单的key-value内存数据库,用hashtable来链接key-value的关系。key不光插入到ttree中，而且还存到hash-table中。hash_table采用了macro：hash-table（uthash.h）`uthash.h的帮助文档:macro：uthash.h帮助文档hashkey-value对的插入:插入之前先HASH_FIND_INT看看，key-value存不存在，如果不存在则可以插，存在的话不能插入。void add_user(int user_id, char name) { struct my_struct s; HASH_FIND_INT(users, &user_id, s); / id already in the hash? / if (s==NULL) { s = (struct my_struct )malloc(sizeof s); s->id = user_id; HASH_ADD_INT( users, id, s ); / id: name of key field / } strcpy(s->name, name);}解析存有key-value格式的文件找到一个key-value格式的实例:xlarge.delfopen()读取文件,读完之后 fclose()关闭。因为待会儿要用strtok来拆开每一行，所以malloc个file_line FILE * fp; fp = fopen("/home/vory/programing/c/key_value_mmdb/xlarge.del",“r”); file_line = malloc(1000 * sizeof(char)); memset(file_line, 0, 1000 * sizeof(char)); …… fclose(fp); fgets获取每一行: char * buf; buf = malloc(sizeof(input)); memset(buf,0,sizeof(input)); while(fgets(input ,256,fp)){ strcpy(buf,input); …… }strtok切割每一行为若干字符串。strtok将目标字符串的符合delim中的元素全部替换为'0’,strtok用了之后，原来的目标代码就被破坏了，因此，新malloc一个接受复制的字符串，将目标字符串strcpy()之后，对复制的字符串进行strtok()操作。用完之后free()。 strcpy(buf,source_string); token = strtok(buf,delim);// printf("%s\n",token); parameter[parametercount] = malloc(sizeof(input)); strcpy(parameter[parametercount],token); parametercount++; token = strtok(NULL,delim);// printf("%s\n",token); parameter[parametercount] = malloc(sizeof(input)); strcpy(parameter[parametercount],token);　实例的xlarge.del 文件的内容大概是这样：每一行分成两部分，KEY 和VALUE被逗号隔开着。41231234,“Teenage Caveman"3061234,“Banger Sisters, The"18861234,“Hope Floats"29381234,“No Looking Back"1288,“Erotic Confessions: Volume 8"2954,“Normal Life"43901234,“Utomlyonnye solntsem"20801234,“Island of Dr. Moreau, The"3019,“One Hell of a Guy"6712341,“Adventures of Pluto Nash, The"33031234,“Pronto"34701234,“Ripper, The"106612341,“Devotion"39481234,“Starship Troopers"32381234,“Polish Wedding"30551234,“Oscar and Lucinda"42391,“Tomcats"1661123411,“Gojira ni-sen mireniamu"10611234,“Devil in a Blue Dress"61612341,“Bully"102612341,“Defenders: Taking the First, The"1650,“Go Fish"43512341,“Black Rose of Harlem"解析从文件读来的每一行：每一行最多解析为２个参数([KEY] [VALUE])。void parse_file(char * string){ char * buf; char * delim; delim = NULL; delim = “,”; char * token; token = NULL; buf = malloc(1000sizeof(char)); memset(buf,0, 1000sizeof(char)); if (!parf0){ parf0 =malloc(500sizeof(char)); } memset(parf0,0, 500sizeof(char)); if (!parf1){ parf1 =malloc(500sizeof(char)); } memset(parf1,0, 500sizeof(char)); strcpy(buf, string); token = strtok(buf, delim); if(token != NULL) { strcpy(parf0, token); } token = strtok(NULL, delim); if (token != NULL){ strcpy(parf1, token); } free(buf);}strtol将字符型的数据转换成long int型:long int strtol(const char nptr,char endptr,int base);strtol不仅可以识别十进制整数，还可以识别其它进制的整数，取决于base参数，base为10，则识别十进制整数。 all_items[bcount].key = strtol(parf0,NULL ,10); bcount++; hash_user_id = strtol(parf0,NULL ,10); strcpy(hash_name,parf1);解析从命令行输入的命令（[COMMANDS] [KEY] [VALUE])从文件读取每一行是 [KEY] [VALUE]的格式，但是从命令行读取是[COMMANDS] [KEY] [VALUE]的格式。我将copy_string,par1，par2，par3定义在了别处。这样就可以解析从stdin输入的句子了，被空格隔开的句子最多分为发出3路给par1，par2，par3。如果stdin输入的句子只包含了一个空格（也就是含有[COMMANDS] [KEY]的结构）则只能被分发为2路给par1和par2.malloc()之后要free(),我在别处free() 了。void parseinput(char string){ char * delim; delim = " “; copy_string = malloc(100sizeof(char)); memset(copy_string,0,100 sizeof(char)); char * token; token = NULL; par1 = malloc(50sizeof(char)); par2 = malloc(50sizeof(char)); par3 = malloc(50sizeof(char)); memset(par1,0,50sizeof(char)); memset(par2,0,50sizeof(char)); memset(par3,0,50sizeof(char)); strcpy(copy_string,string); printf("%s is copystring .\n “,copy_string); printf("%s is string . \n”,string); token = strtok(copy_string,delim); if (token != NULL){ printf("%s is token1 \n”,token); strcpy(par1,token); } token = strtok(NULL,delim); if (token != NULL){ printf("%s is token2 \n”,token); strcpy(par2,token); } token = strtok(NULL,delim); if (token != NULL){ printf("%s is token3 \n”,token); strcpy(par3,token); } free(copy_string);}初始化T-tree#define ttree_init(ttree, num_keys, is_unique, cmpf, data_struct, key_field) _ttree_init(ttree, num_keys, is_unique, cmpf, offsetof(data_struct, key_field))int __ttree_init(Ttree ttree, int num_keys, bool is_unique, ttree_cmp_func_fn cmpf, size_t key_offs);……….. ret = ttree_init(&ttree, 8, false, __cmpfunc, struct item, key); if (ret < 0) { fprintf(stderr, “Failed to initialize T-tree. [ERR=%d]\n”, ret); free(all_items); exit(EXIT_FAILURE); }将读取的每一行插入ttree，并将key-value插入hashtable在一个循环中解析每一行，当真个文件的所有行都读完则跳出循环。 while (fgets(file_line, 1000, fp)) { parse_file(file_line); all_items[bcount].key = strtol(parf0, NULL, 10); hash_name = malloc(500 * sizeof(char)); memset(hash_name, 0, 500 * sizeof(char)); hash_user_id = strtol(parf0, NULL, 10); strcpy(hash_name, parf1); s = find_user(hash_user_id); if (s == NULL) { add_user(hash_user_id, hash_name); } free(hash_name); memset(file_line, 0, 1000 * sizeof(char)); } for (i = 0; i < num_keys; i++) { ret = ttree_insert(&ttree, &all_items[i]); if (ret < 0) { fprintf(stderr, “Failed to insert item %d with key %ld! [ERR=%d]\n”, i, all_items[i].key, ret); free(all_items); exit(EXIT_FAILURE); } } 打印出ttree的所有key for (i = 0; i < num_keys; i++) { printf("%ld “, all_items[i].key); }给ttree的所有key排序从小到大排序，递归实现。 printf("\nSorted keys:\n”); printf(”{ “); tnode = ttree_node_leftmost(ttree.root); while (tnode) { tnode_for_each_index(tnode, i) { printf("%d “, (int ) tnode_key(tnode, i)); } tnode = tnode->successor; } printf(”}\n”);程序结束前free()，释放内存空间ttree_destroy(&ttree);free(all_items);附件&代码github代码所有的代码参考文献[1].Tobin J. Lehman and Michael J. Carey. 1986. A Study of Index Structures for Main Memory Database Management Systems. In Proceedings of the 12th International Conference on Very Large Data Bases (VLDB ‘86), Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, and Yahiko Kambayashi (Eds.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 294-303.[2].Kong-Rim Choi and Kyung-Chang Kim, “T-tree: a main memory database index structure for real time applications,” Proceedings of 3rd International Workshop on Real-Time Computing Systems and Applications, Seoul, South Korea, 1996, pp. 81-88.doi: 10.1109/RTCSA.1996.554964[3].wikipidia about T-tree[4].An Open-source T-tree Library ...

节点定义class Node(object): def init(self, left_child, right_child, value): self._left_child = left_child self._right_child = right_child self._value = value @property def left_child(self): return self._left_child @property def right_child(self): return self._right_child @left_child.setter def left_child(self, value): self._left_child = value @right_child.setter def right_child(self, value): self._right_child = value @property def value(self): return self._value @value.setter def value(self, value): self._value = value二叉树定义class Tree(object): def init(self, value): self._root = Node(None, None, value=value) @property def root(self): return self._root先序遍历递归方式’‘‘先序遍历，递归方式’‘‘def preoder(root): if not isinstance(root, Node): return None preorder_res = [] if root: preorder_res.append(root.value) preorder_res += preoder(root.left_child) preorder_res += preoder(root.right_child) return preorder_res非递归方式’‘‘先序遍历，非递归方式’‘‘def pre_order_not_recursion(root): if not isinstance(root, Node): return None stack = [root] result = [] while stack: node = stack.pop(-1) if node: result.append(node.value) stack.append(node.right_child) stack.append(node.left_child) return result中序遍历递归方式’‘‘中序遍历，递归方式’‘‘def middle_order(root): if not isinstance(root, Node): return None middle_res = [] if root: middle_res += middle_order(root.left_child) middle_res.append(root.value) middle_res += middle_order(root.right_child) return middle_res非递归方式’‘‘中序遍历，非递归方式’‘‘def middle_order_bot_recursion(root): if not isinstance(root, Node): return None result = [] stack = [root.right_child, root.value, root.left_child] while stack: temp = stack.pop(-1) if temp: if isinstance(temp, Node): stack.append(temp.right_child) stack.append(temp.value) stack.append(temp.left_child) else: result.append(temp) return result后序遍历递归方式’‘‘后序遍历，递归方式’‘‘def post_order(root): if not isinstance(root, Node): return None post_res = [] if root: post_res += post_order(root.left_child) post_res += post_order(root.right_child) post_res.append(root.value) return post_res非递归方式’‘‘后序遍历，非递归方式’‘‘def post_order_not_recursion(root): if not isinstance(root, Node): return None stack = [root.value, root.right_child, root.left_child] result = [] while stack: temp_node = stack.pop(-1) if temp_node: if isinstance(temp_node, Node): stack.append(temp_node.value) stack.append(temp_node.right_child) stack.append(temp_node.left_child) else: result.append(temp_node) return result分层遍历’‘‘分层遍历，使用队列实现’‘‘def layer_order(root): if not isinstance(root, Node): return None queue = [root.value, root.left_child, root.right_child] result = [] while queue: temp = queue.pop(0) if temp: if isinstance(temp, Node): queue.append(temp.value) queue.append(temp.left_child) queue.append(temp.right_child) else: result.append(temp) return result计算二叉树结点个数’‘‘计算二叉树结点个数，递归方式NodeCount(root) = NodeCount(root.left_child) + NodeCount(root.right_child)‘‘‘def node_count(root): if root and not isinstance(root, Node): return None if root: return node_count(root.left_child) + node_count(root.right_child) + 1 else: return 0’‘‘计算二叉树结点个数，非递归方式借用分层遍历计算’‘‘def node_count_not_recursion(root): if root and not isinstance(root, Node): return None return len(layer_order(root))计算二叉树深度’‘‘计算二叉树深度，递归方式tree_deep(root) = 1 + max(tree_deep(root.left_child), tree_deep(root.right_child))‘‘‘def tree_deep(root): if root and not isinstance(root, Node): return None if root: return 1 + max(tree_deep(root.left_child), tree_deep(root.right_child)) else: return 0’‘‘计算二叉树深度，非递归方法同理参考分层遍历的思想’‘‘def tree_deep_not_recursion(root): if root and not isinstance(root, Node): return None result = 0 queue = [(root, 1)] while queue: temp_node, temp_layer = queue.pop(0) if temp_node: queue.append((temp_node.left_child, temp_layer+1)) queue.append((temp_node.right_child, temp_layer+1)) result = temp_layer + 1 return result-1计算二叉树第k层节点个数’‘‘计算二叉树第k层节点个数，递归方式kth_node_count(root, k) = kth_node_count(root.left_count, k-1) + kth_node_count(root.right_count, k-1)‘‘‘def kth_node_count(root, k): if root and not isinstance(root, Node): return None if not root or k <= 0: return 0 if k == 1: return 1 return kth_node_count(root.left_child, k-1) + kth_node_count(root.right_child, k-1)‘‘‘计算二叉树第K层节点个数，非递归方式’‘‘def kth_node_count_not_recursion(root, k): if root and not isinstance(root, Node): return None if not root or k <= 0: return 0 if k == 1: return 1 queue = [(root, 1)] result = 0 while queue: temp_node, temp_layer = queue.pop(0) if temp_node: if temp_layer == k: result += 1 elif temp_layer > k: return result else: queue.append((temp_node.left_child, temp_layer+1)) queue.append((temp_node.right_child, temp_layer+1)) return result计算二叉树叶子节点个数’‘‘计算二叉树叶子节点个数，递归方式关键点是叶子节点的判断标准，左右孩子皆为None’‘‘def leaf_count(root): if root and not isinstance(root, Node): return None if not root: return 0 if not root.left_child and not root.right_child: return 1 return leaf_count(root.left_child) + leaf_count(root.right_child)判断两个二叉树是不是相同’‘‘判断两个二叉树是不是相同，递归方式isSame(root1, root2) = (root1.value == root2.value) and isSame(root1.left, root2.left) and isSame(root1.right, root2.right)‘‘‘def is_same_tree(root1, root2): if not root1 and not root2: return True if root1 and root2: return (root1.value == root2.value) and \ is_same_tree(root1.left_child, root2.left_child) and \ is_same_tree(root1.right_child, root2.right_child) else: return False判断是否为二分查找树BST’‘‘判断是否为二分查找树BST，递归方式二分查找树的定义搞清楚，二分查找树的中序遍历结果为递增序列’‘‘def is_bst_tree(root): if root and not isinstance(root, Node): return None def is_asc(order): for i in range(len(order)-1): if order[i] > order[i+1]: return False return True return is_asc(middle_order_bot_recursion(root))测试方法if name == “main”: tree = Tree(1) tree1 = Tree(1) node6 = Node(None, None, 7) node5 = Node(None, None, 6) node4 = Node(None, None, 5) node3 = Node(None, None, 4) node2 = Node(node5, node6, 3) node1 = Node(node3, node4, 2) tree.root.left_child = node1 tree.root.right_child = node2 tree1.root.left_child = node2 tree1.root.right_child = node2 print(is_bst_tree(tree.root)) ...

这一篇是接上一篇文章二叉树的基本运算二叉树的遍历二叉树遍历分为三种：前序、中序、后序:前序遍历：根结点 -> 左子树 -> 右子树中序遍历：左子树 -> 根结点 -> 右子树后序遍历：左子树 -> 右子树 -> 根结点另外还有一种层次遍历，即每一层都从左向右遍历。譬如，对于下面的二叉树前序遍历：abdefgc中序遍历：debgfac后序遍历：edgfbca层次遍历：abcdfeg实现方法因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点中序遍历go实现// 中序遍历，用栈实现func inOrderBinaryTree1(root *BinaryTreeNode) { if root == nil { return } stack := []*BinaryTreeNode{} top := -1 for top >= 0 || root != nil { for root != nil { stack = append(stack, root) top++ root = root.lChild } item := stack[top] stack = stack[:top] top– // 出栈 fmt.Print(item.data) if item.rChild != nil { root = item.rChild } }} ...

二叉树简介基本结构：function TreeNode(x) { this.val = x; this.left = null; this.right = null;}二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。题目1 二叉树的镜像1.1 题目描述操作给定的二叉树，将其变换为源二叉树的镜像。输入描述:二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 51.2 解题思路递归交换二叉树两棵字树的位置。1.3 代码function Mirror(root){ if(root){ const temp = root.right; root.right = root.left; root.left = temp; Mirror(root.right); Mirror(root.left); }}题目2 从上往下打印二叉树2.1 题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。2.2 解题思路1.借助队列先进先出的数据结构2.让二叉树每层依次进入队列3.依次打印队列中的值2.3 代码 function PrintFromTopToBottom(root) { const queue = []; const print = []; if(root != null){ queue.push(root); } while (queue.length > 0) { const current = queue.shift(); print.push(current.val); if (current.left) { queue.push(current.left); } if (current.right) { queue.push(current.right); } } return print; } ...

二叉树简介基本结构：function TreeNode(x) { this.val = x; this.left = null; this.right = null;}二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。题目1 二叉树遍历1.1 题目描述给定一棵二叉树的前序遍历和中序遍历，求其后序遍历输入描述:两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示：A，B，C….最多26个结点。输出描述:输入样例可能有多组，对于每组测试样例，输出一行，为后序遍历的字符串。样例：输入ABCBACFDXEAGXDEFAG输出BCAXEDGAF1.2 解题思路前序遍历：跟节点 + 左子树前序遍历 + 右子树前序遍历中序遍历：左子树中序遍历 + 跟节点 + 右字数中序遍历后序遍历：左子树后序遍历 + 右子树后序遍历 + 跟节点1.前序遍历的头部为跟节点2.中序遍历以跟节点分割，左侧为左子中序遍历，右侧为右子树中序遍历3.根据中序遍历得到的左子树右子树的长度，得到左子树的前序遍历和右子树的前序遍历1.3 代码let pre;let vin; while((pre = readline())!=null){ vin = readline(); print(getHRD(pre,vin));} function getHRD(pre, vin) { if (!pre) { return ‘’; } if (pre.length === 1) { return pre; } const head = pre[0]; const splitIndex = vin.indexOf(head); const vinLeft = vin.substring(0, splitIndex); const vinRight = vin.substring(splitIndex + 1); const preLeft = pre.substring(1, splitIndex + 1); const preRight = pre.substring(splitIndex + 1); return getHRD(preLeft, vinLeft) + getHRD(preRight, vinRight) + head;题目2 二叉树重建2.1 题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。2.2 解题思路思路和题目1相似。根据前序遍历和中序遍历的结果可以拿到：左子中序遍历和右侧为右子树中序遍历左子树的前序遍历和右子树的前序遍历然后递归左子树和右子树的完成重建。2.3 代码 function reConstructBinaryTree(pre, vin) { if(pre.length === 0){ return null; } if(pre.length === 1){ return new TreeNode(pre[0]); } const value = pre[0]; const index = vin.indexOf(value); const vinLeft = vin.slice(0,index); const vinRight = vin.slice(index+1); const preLeft = pre.slice(1,index+1); const preRight = pre.slice(index+1); const node = new TreeNode(value); node.left = reConstructBinaryTree(preLeft, vinLeft); node.right = reConstructBinaryTree(preRight, vinRight); return node; } ...

关于二叉树的遍历，使用栈递归或者仿栈循环都是需要O(N)的空间，Morris Traversal保证了空间为O(1)，时间还是O(N)（比原来多了一遍）。这里只介绍inOrder顺序。思路：对每一个cur节点，优先找到一个pre节点，这个pre节点的作用是，当后续cur节点遍历 到这个位置时，可以直接通过这个pre节点返回它需要返回的位置。例如： 6 / \ 4 8 / \ 2 5上面当cur节点在6的时候，pre节点会在5，因为后面当cur节点遍历到5的时候，可以通过pre节点直接返回6当cur节点再4的时候，pre节点会在2，当后面cur到2的时候，可以直接返回4pre找到了，是通过什么返回呢，因为不能修改二叉树结构，也不能使用堆栈记录。通过mirror(镜像)，也就是说，当找到pre的时候（每个pre的右节点确保为null），在它的右节点创建一个镜像节点，这个镜像节点直接指向当前的cur节点。这个操作是不占用空间的，因为只是互相引用。例如：当上面的cur为6，pre为5，那么设置pre.right=cur，感觉上是这样： 6 / \ 4 8 / \ 2 5 \ 6 / \ 4 8 …其实并没有多出来那一块，只是5引用到6罢了 6 / ↑ \ 4 ↑ 8 / \↑ 2 5 理解了这些，那么后续就简单了，当cur遍历到pre的时候并且打印后，将pre新增的引用删除恢复原来的树便可。代码：function morrisTraversal(root){ let cur=root,pre while(cur!=null){ // 当左为空，直接打印 if(cur.left==null){ console.log(cur.val) cur=cur.right }else{ // 当左不为空，先去找 pre pre=cur.left while(pre.right!=null && pre.right!==cur){ pre=pre.right } // 建立引用，用于返回 if(pre.right==null){ pre.right=cur cur=cur.left }else{ // 删除引用 console.log(cur.val) pre.right=null cur=cur.right } } }} ...

题目Return any binary tree that matches the given preorder and postorder traversals.Values in the traversals pre and post are distinct positive integers.Example 1:Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]Output: [1,2,3,4,5,6,7]Note:1 <= pre.length == post.length <= 30pre[] and post[] are both permutations of 1, 2, …, pre.length.It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.讲解先序遍历和后序遍历无法确定一颗二叉树，所以这里有可能返回多种不同的树，但只要是正确的就行。解这道题的关键在于分割左右子树，先序遍历中紧跟根节点后的也有可能不是左子树，但如果是这样的话，后续遍历中也不会有左子树，那么右子树的根节点就会在两种遍历中都挨着总根节点。所以思路就出来了，我们在先序遍历中拿到根节点后面的那个节点，然后在后序遍历中找到这个节点，这个点就在后序遍历中分割出了左右子树。递归之。Java代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode constructFromPrePost(int[] pre, int[] post) { return constructFromPrePost(pre, 0, pre.length-1, post, 0, post.length-1); } private TreeNode constructFromPrePost(int[] pre, int preLeft, int preRight, int[] post, int postLeft, int postRight){ if(preLeft>preRight || postLeft>postRight){ return null; }else if(preLeft==preRight){ return new TreeNode(pre[preLeft]); } TreeNode root = new TreeNode(pre[preLeft]); for(int i=postRight-1;i>=postLeft;i–){ if(post[i]==pre[preLeft+1]){ root.left = constructFromPrePost(pre, preLeft+1, preLeft+1+i-postLeft, post, postLeft, i); root.right = constructFromPrePost(pre, preLeft+2+i-postLeft, preRight, post, i+1, postRight-1); } } return root; }} ...

题目Given a binary tree, find the leftmost value in the last row of the tree.Example 1:Input: 2 / \ 1 3Output:1Example 2:Input: 1 / \ 2 3 / / \ 4 5 6 / 7Output:7Note: You may assume the tree (i.e., the given root node) is not NULL.题目地址讲解这道题感觉挺简单的，首先我想到的是一定要选深度最大的节点，然后他要最左边的，那么我们可以先右后左的进行遍历，最后左边就可以覆盖右边了。java代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { private int result; private int maxDepth=0; public int findBottomLeftValue(TreeNode root) { inOrder(root, 0); return result; } private void inOrder(TreeNode root, int depth){ if(root==null){ return; } if(maxDepth<=depth){ maxDepth=depth; result = root.val; } if(root.right!=null){ inOrder(root.right, depth+1); } if(root.left!=null){ inOrder(root.left, depth+1); } }} ...

题目Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.For example,Given the tree: 4 / \ 2 7 / \ 1 3And the value to search: 2You should return this subtree: 2 / \ 1 3In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.题目地址讲解要注意一下的是，如果我们searchBST作为递归函数，我们就要返回一个TreeNode类型，虽然返回，但我们不一定会用到。如果我们找到了，就把treeNode标记为结果结点。Java代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { private TreeNode treeNode; public TreeNode searchBST(TreeNode root, int val) { if(root==null){ return treeNode; } if(root.val == val){ treeNode = root; } searchBST(root.left, val); searchBST(root.right, val); return treeNode; }} ...

题目For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.Write a function that determines whether two binary trees are flip equivalent. The trees are given by root nodes root1 and root2.Example 1:Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]Output: trueExplanation: We flipped at nodes with values 1, 3, and 5.Note:Each tree will have at most 100 nodes.Each value in each tree will be a unique integer in the range [0, 99].题目地址讲解这道题考察的依旧是递归，其实跟树有关的大部分题都是递归。树对应多叉递归，栈对应线性递归。然后递归重要的就一个点：结束条件。Java代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public boolean flipEquiv(TreeNode root1, TreeNode root2) { if(root1==null && root2==null){ return true; }else if((root1==null&&root2!=null) || (root1!=null&&root2==null) || (root1.val!=root2.val)){ return false; } return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) || (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left)); }} ...

Merge Two Binary TreesGiven two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.Example 1:Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: Merged tree: 3 / \ 4 5 / \ \ 5 4 7Note: The merging process must start from the root nodes of both trees.这一题主要考察的点有两个：二叉树的遍历分类讨论的能力java代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if(t1==null && t2==null){ return null; }else if(t1==null && t2!=null){ t1 = new TreeNode(t2.val); t1.left = mergeTrees(null, t2.left); t1.right = mergeTrees(null, t2.right); }else if(t1!=null && t2!=null){ t1.val = t1.val+t2.val; t1.left = mergeTrees(t1.left, t2.left); t1.right = mergeTrees(t1.right, t2.right); }else{ t1.left = mergeTrees(t1.left, null); t1.right = mergeTrees(t1.right, null); } return t1; }}

Binary Tree PruningWe are given the head node root of a binary tree, where additionally every node’s value is either a 0 or a 1.Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)Example 1:Input: [1,null,0,0,1]Output: [1,null,0,null,1]Explanation: Only the red nodes satisfy the property “every subtree not containing a 1”.The diagram on the right represents the answer.Example 2:Input: [1,0,1,0,0,0,1]Output: [1,null,1,null,1]Example 3:Input: [1,1,0,1,1,0,1,0]Output: [1,1,0,1,1,null,1]Note:The binary tree will have at most 100 nodes.The value of each node will only be 0 or 1.题目地址这道题考察的应该是二叉树的遍历，核心的解法在于先将叶子0节点变为null，然后就会发现祖先节点可以用同样的方法递归的解决。java代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode pruneTree(TreeNode root) { if(root==null) return root; root.left = pruneTree(root.left); root.right = pruneTree(root.right); if(root.val==0 && root.left==null && root.right==null){ root=null; } return root; }}