二叉树

先把二叉树的四种遍历模式和后果记录下来，而后倒推各种解法，如下图所示： 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)如果您感觉本文有用，请点个“在看” ...