文章目录
什么是树？
树形结构的概念
树是一种非线性的数据结构，它是由n(n>=0)个优先节点组成一个具有层次关系的集合。把它叫作树，是因为它看起来像一棵树，也就是说它是根朝上，而叶朝下。
它具有以下特点：
1、有一个特殊的结点，称为根结点，根节点没有前驱结点
2、除根结点外，其余结点被分成 M (M > 0) 个互不相交的集合 T1、 T2、…、 Tm，其中每一个集合 Ti（1 <= i <= m）又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
3、 树是递归定义的。(这个等到 具体讲二叉树的时候会讲到的)
注意：树形结构中，子树之间不能有交集，否则就不是树形结构。
重要概念
结点的度：一个结点含有子树的个数；如上图：A的度为6。
树的度：一棵树中，所有结点度的最大值称为树的度；如上图：树的度为6。
叶子结点或终端结点：度为0的节点成为叶节点；如上图：B、C、H、I、P、Q、K、L、M、N都是叶子结点。
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点/双亲节点；如上图：A 是 B 的父结点。还有很多就不说了。
孩子结点或子结点：一个结点 含有的子树的根结点 称为 该节点 的 子结点；如上图： B 是 A 的孩子结点
根结点：一棵树中，没有双亲结点的结点；如上图：A
结点的层次：从根开始定义起，根为第一层，根的子结点为第2层，依次类推。
树的高度或深度：树中最大深度 ，即为高度；如上图：树的高度为 4,最大深度也为 4。但两者是不同的定西。
只有：当深度最大时， 深度才能说是高度。
非终端结点或分支结点： 度不为0的节点；如上图：D E F G J 都是分支结点。【简单来说：除了叶子结点【度为0的结点】，其它结点都是分支结点/非终端结点】
兄弟结点：具有相同父结点 的 节点 互称为兄弟结点；如上图：B C 互为兄弟结点。
堂兄弟结点：双亲/父 在同一层的结点互为堂兄弟； 如上图：H I 互为堂兄弟结点。
结点的祖先：从该节点出发，可以经过所有分支上的节点；如上图：A 是 所有节点的祖先。
子孙：以某个结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A节点的子孙。
森林： 由 m（m >= 0）棵 互不相交的树组成的集合称为森林
树的表示形式
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式.
如：双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。
我们这里就简单的了解其中最常用的孩子兄弟表示法。
这里，我们在额外的讲一下 双亲表示法，就是 孩子兄弟法，加了一个存储空间，用来存储自身的父结点
树的应用
文件系统管理（目录 和 文件）
试想一下：我们的电脑常有空文件夹，点进去，就没有东西点了。对不对？那这空文件夹是不是就可以看作是叶子结点！【没有子结点，或者“度”为零嘛。】再来举一个例子：
二叉树
概念
一棵二叉树是结点的一个有限集合，该集合：
1、可能为 空
2、可能是由一个根结点加上两棵别称为 左子树 和 右子树 的 二叉树组成。
二叉树 跟我们前面讲的树的区别就在于：二叉树 的 每个结点，最多只能有 两个 “孩子”/子树.。最少 零个。
也就是说：一棵树，如果是二叉树，那么它的每棵子树都是 二叉树【都有左子树 和 右子树】。
总结
- 二叉树不存在度大于2 的结点
2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树为有序树。
注意：对于任意的二叉树都是由以下几种情况复合而成的
上图的这四棵树都是二叉树
两种特殊的二叉树
1、满二叉树：一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说：如果一棵二叉树的层数为K，且结点总数是 2的k次方-1，则它就是满二叉树。
2、完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引申出来的。对于深度为K的，有n个节点的二叉树，当其每一个结点都与深度为k的满二叉树中编号从 0 值 n -1 的结点 一一对应时称之为完全二叉树。值得注意的是 满二叉树 是一种特殊的 完全二叉树。
【简单来说： 给二叉树编号，根结点为0，然后下一层次 从左往右，依次编号。中间不能有间断，依次类推】
二叉树性质
性质1、 若规定根结点的层数为1，则一棵非空二叉树的第i层上，最多有 2的 (i - 1)次方。【这个我们在前面推导满二叉树的时候，已经出来了 2的（k-1）次方】
性质2、若规定只有根结点的二叉树的深度为1，则深度为k的二叉树的最大结点数是 2的K次方减一（k>=0）。【就是满二叉树】
性质3、对于任何一棵二叉树，如果其 叶结点个数 为 n0,度为2的非叶结点个数为 n2，则有 n0 = n2 + 1。【也就是说：叶结点的个数 总是比 非叶结点的个数多一个】得出结论：任何一棵二叉树的叶子结点 比 度为2的节点 多一个。
来看三个练习题
性质4、具有n个结点的完全二叉树的深度 k 为 log以为2底的（n+1）上取整
再来看个练习题
性质5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i
的结点有：
若 i > 0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
若2i+1<n，左孩子序号：2i+1，否则无左孩子
若2i+2<n，右孩子序号：2i+2，否则无右孩子
二叉树存储
二叉树的存储结构分为：顺序存储 和 类似于链表的链式存储。
这里，我们讲链式存储。
二叉树的链式存储是通过一个一个的节点引用起来的。常见的表示方式有二叉 和 三叉表示方式。
【二叉 ： 孩子表示法；三叉 ：孩子双亲表示法】
模拟实现二叉树
提前说明：二叉树的构建是一个非常复杂的过程，因为目前作者对二叉树的理解，还不是很深。所以，我们先会创建一个二叉树，但是这种创建方式，很LOW， 只是为了应付前期使用，比较简单，不是正确的常用创建方式。
准备工作
构造二叉树节点 - （孩子表示法）
构建一棵这样的二叉树
debug【调试效果图】
二叉树最重要的功能 - 遍历二叉树 - （一级标题 更显重要。）
学习二叉树结构，最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结
点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题【打印节点值，求节点个数等】。所有的二叉树相关的题目，基本上都是需要通过某种遍历去解题的。
1. NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树
2. LNR：中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树
它的遍历顺序 就是 左子树 》》 根结点 》》 右子树
3. LRN：后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点
遍历顺序： 左子树 》》 右子树 》》 根结点
小结
前中后，无论是哪一种遍历，都是按照下面图的路线，来走的，只是打印的顺序不同而已，
练习
写出下面二叉树的 前中后排序的 序列
前序遍历：A B D E H C F G
中序遍历：D B H E A F C G
后序遍历：D H E B F G C A
程序实现 - 前中后序遍历
接着模拟实现二叉树，完成其遍历功能
前序遍历
拓展
二叉树的题 天生就是用递归来写的。【90%】
剩余 10%，使用非递归来解决问题。【只针对部分题】
其实所有的递归 都是 跟栈有关系的。
中序遍历
与前序同理，就是打印顺序不同.
// 中序序遍历publicvoidinorderTraversal(BTNode root){if(root ==null){return;}inorderTraversal(root.left);System.out.print(root.val +" ");inorderTraversal(root.right);}
后序遍历
与前序同理，就是打印顺序不同.
// 后序遍历publicvoidpostorderTraversal(BTNode root){if(root ==null){return;}postorderTraversal(root.left);postorderTraversal(root.right);System.out.print(root.val +" ");}
实战题 - LeetCode - 144. 二叉树的前序遍历 - 遍历思维
这题，你可以直接将我们刚才的程序，复制粘贴。
唯一需要注意的就是
不过也很好解决。new一个 List 的嘛。反正它只用来存储前序遍历的结果序列。
其次，就是把输出语句 换成 add 添加 语句，将遍历的结果存入
代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{List<Integer> list;publicList<Integer>preorderTraversal(TreeNode root){
list =newArrayList<>();preorder(root);return list;}publicvoidpreorder(TreeNode root){if(root ==null){return;}
list.add(root.val);preorder(root.left);preorder(root.right);}}
实战题 - LeetCode - 94. 二叉树的中序遍历 - 遍历思维
做法 完全一样，改变一下，add 添加数据的代码位置就行了
代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{List<Integer> list;publicList<Integer>inorderTraversal(TreeNode root){
list =newArrayList<>();inorder(root);return list;}publicvoidinorder(TreeNode root){if(root ==null){return;}inorder(root.left);
list.add(root.val);inorder(root.right);}}
实战题 - LeetCode - 145. 二叉树的后序遍历- 遍历思维
我就直接上代码。。。。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{List<Integer> list;publicList<Integer>postorderTraversal(TreeNode root){
list =newArrayList<>();postorder(root);return list;}publicvoidpostorder(TreeNode root){if(root ==null){return;}postorder(root.left);postorder(root.right);
list.add(root.val);}}
拓展 ： 实战题 - LeetCode - 144. 二叉树的前序遍历 - 子问题思路
将二叉树 整体分为 根结点，左子树 和 右子树 三部分，将其按照前序的遍历顺序进行添加。
代码如下
classSolution{publicList<Integer>preorderTraversal(TreeNode root){List<Integer> list =newArrayList<>();if(root ==null){return list;}
list.add(root.val);List<Integer> treeLeft =preorderTraversal(root.left);
list.addAll(treeLeft);List<Integer> treeRight =preorderTraversal(root.right);
list.addAll(treeRight);return list;}}
代码分析
4. 层序遍历
除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在
层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层
上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历
练习题
现在开始实现二叉树所具有的基本功能
获取二叉树的节点个数
获取叶子结点个数
获取第K层节点的个数 - 子问题思路
获取二叉树的高度 - 子问题思路
检测值为value的元素是否存在
我们都知道在数组当中 查找一个数据：遍历数组，依次查找。
如果是链表中，是不是也是需要从头节点开始遍历比较，确认是不是存在的。
而现在是二叉树，是不是也需要遍历二叉树紫红的节点，确定某一个节点的值，是不是我们要找的。
最简单就是运用前序遍历来实现。先判断根结点值是否与 value值相等，其次 左子树，最后是右子树。
// 检测值为value的元素是否存在publicBTNodefind(BTNode root,char value){if(root ==null){returnnull;}if(root.val == value){// 判断根结点是不是 指定的数据return root;}BTNode node1 =find(root.left,value);// 查找 左子树 是有存在 指定value值的节点【找到了，返回其引用，否，则返回null】BTNode node2 =find(root.right,value);// 查找 右子树 是有存在 指定value值的节点【找到了，返回其引用，否，则返回null】return node1 ==null? node2:node1;// 如果 node1 为 null，说明左子树没有指定value值的节点，返回 node2【右子树的查找的结果】// 如果 node2 也没有，也没有关系，反正都是返回null，node2找到了更好。返回其节点的引用}
判断一棵树是不是完全二叉树
拓展： 队列中 入队为元素为 null，队列也是有大小的。
与面试相关的二叉树OJ题型
LeetCode - 100. 相同的树
题目解析
注意我框选的题干部分【如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。】 它的意思： 两棵二叉树的节点位置 与 节点值 都必须一模一样。 两个条件中，只要有一个条件不符合。那么，这棵二叉树就不说是相同的树。
解题思维
利用遍历思想 去完成这道题：就是 使用同一种遍历方式，来遍历两棵二叉树节点，如果两棵树的节点值，有一组不相等就返回false。
但是！我们需要注意几个特殊情况！
情况1：
两棵二叉树为 空树【两棵二叉树的根结点为 null】
情况2：
一棵二叉树为null，另一棵不为null。
代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicbooleanisSameTree(TreeNode p,TreeNode q){if(p ==null&& q ==null){// 两棵二叉树都为空树returntrue;}// 两棵儿茶素中，有一颗树为空树if((p !=null&& q ==null)||(p ==null&& q !=null)){returnfalse;}// 判断 两棵二叉树中，两个相对应的位置节点val值是否相同【宏观：判断根结点 是否相同】if(p.val != q.val){returnfalse;}// 宏观：// 走到这里 说明两棵二叉树的头节点相同。接着，就是遍历 两棵二叉树的 左右子树。// 必须 两棵二叉树的左右子树都相等【true】。再结合根结点。【true】// 这两棵二叉树才能算是相同的树returnisSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}}
LeetCode - 572. 另一棵树的子树
题目解析
简单来说： 在 根结点为 root 的 二叉树中，寻找有没有 一棵 与 根结点为subRoot的二叉树 相同的树。
解题思维
既然是寻找相同的树，那么，肯定是需要一个方法来判断 相同的树。【上一题的代码，就可以直接复制过来，作为一个判断相同树的方法来使用】
subRoot 为 root 的子树，无非就是以下几种情况：
1、root 与 subRoot 是一棵相同的树
2、 subRoot 是 root 的 左子树 ，或者说 是 左子树的一部分，
3、 subRoot 是 root 的 右子树 ，或者说 是 右子树的一部分，注意：以上这些操作，都可以交由我们的判断相同的方法来操作。但这不意味着我们可以什么都不用做！
代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicbooleanisSameTree(TreeNode p,TreeNode q){if(p ==null&& q ==null){// 两棵二叉树都为空树returntrue;}// 两棵儿茶素中，有一颗树为空树if((p !=null&& q ==null)||(p ==null&& q !=null)){returnfalse;}// 判断 两棵二叉树中，两个相对应的位置节点val值是否相同【宏观：判断根结点 是否相同】if(p.val != q.val){returnfalse;}// 宏观：// 走到这里 说明两棵二叉树的头节点相同。接着，就是遍历 两棵二叉树的 左右子树。// 必须 两棵二叉树的左右子树都相等【true】。再结合根结点。【true】// 这两棵二叉树才能算是相同的树returnisSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}publicbooleanisSubtree(TreeNode root,TreeNode subRoot){if(root ==null){return subRoot!=null?false:true;}// 判断 是否是同一棵树if(isSameTree(root,subRoot)){returntrue;}// 判断 subRoot是否 是 root的左子树 或者 是左子树的一部分if(isSubtree(root.left,subRoot)){returntrue;}// 判断 subRoot是否 是 root的右子树 或者 是右子树的一部分if(isSubtree(root.right,subRoot)){returntrue;}returnfalse;}}
LeetCode - 104. 二叉树的最大深度
这题就是我们前面实现的 求二叉树高度功能。【高度 等价于 二叉树的最大深度】
这里我就直接上代码了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicintmaxDepth(TreeNode root){if(root ==null){return0;}returnMath.max(maxDepth(root.left),maxDepth(root.right))+1;}}
LeetCode - 110. 平衡二叉树
题目解析
题目的意思： 让我们去计算 这棵二叉树的左右子树的高度。其高度差不超过 1。
唯一需要注意的是：平衡二叉树 不仅仅是 左右子树 是这么个情况，还需要把左右子树 看作一个 二叉树，而且也必须是一个平衡二叉树。
也就是说：平衡二叉树 的 左右子树高度差 不超过 1，且如果将左右子树看作 是 一棵单独二叉树 ，也是一棵平衡二叉树。
代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
时间复杂度 O(N)
空间复杂度 O(log2N)classSolution{publicbooleanisBalanced(TreeNode root){if(root ==null){returntrue;}int leftHeight =getHeight(root.left);// 获取 左子树高度int rightHeight =getHeight(root.right);// 获取 右子树高度// 判断 左右子树的高度差不能超过 1。另外，左右子树自身 也要满足这个条件。returnMath.abs(leftHeight - rightHeight)<=1&&isBalanced(root.left)&&isBalanced(root.right);}publicintgetHeight(TreeNode root){// 计算根结点为“root”的二叉树高度if(root ==null){return0;}returnMath.max(getHeight(root.left),getHeight(root.right))+1;}}
进阶
代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicbooleanisBalanced(TreeNode root){if(root ==null){returntrue;}returngetHeight(root)>-1;}publicintgetHeight(TreeNode root){if(root ==null){return0;}intL=getHeight(root.left);// 左子树高度intR=getHeight(root.right);// 右子树高度if(L>=0&&R>=0&&Math.abs(L-R)<=1){returnMath.max(L,R)+1;}else{// 说明不平衡return-1;}}}
LeetCode - 101. 对称二叉树
题目解析
简单来说：以根结点为分界线，将二叉树的左右子树分割开来，并以此线 作为对称轴。
对称简单来说：将这上图看作一张纸，沿着 对称轴 折叠，你会发现 左右子树的节点完美重合【位置和值都是】
解题思维
简单来说：以二叉树的根结点 1 为 分割线， 去判断 左右子树 节点的值是否对称。
对称图如下：
但是有几个特殊情况需要注意！
1、二叉树为空树，根结点为null。【空树也是树，也算对称树】
2、二叉树只有一个根结点，也算对称二叉树【左右两个空子树】
3、 二叉树的左右子树中：有一个为空子树【非对称子树】
代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicbooleanisSymmetric(TreeNode root){// 二叉树为 空树if(root ==null){returntrue;}returnisSymmetricChild(root.left,root.right);}publicbooleanisSymmetricChild(TreeNodeL,TreeNodeR){// 树的根结点 左右子树为nullif(L==null&&R==null){returntrue;}// 二叉树的左右子树有一棵子树为空树if((L==null&&R!=null)||(L!=null&&R==null)){returnfalse;}// 继续判断：两棵树中 对称节点的值【左对右，右对左】if(L.val ==R.val){returnisSymmetricChild(L.left,R.right)&&isSymmetricChild(L.right,R.left);}returnfalse;}}
牛客题霸 - KY11 二叉树遍历
题目解析
简单来说：根据所给出 二叉树 前序遍历序列，构造出一棵二叉树。对其进行 中序遍历，输出结果。
解题思维
首先，我们先根据 它所给的 前序遍历序列 和 关键条件【# 代表 空树】 ，根据示例的 数据，来 推导构造出一棵二叉树
难点：是推导出来了，也画出来了，但是代码具体如何实现？
答案：既然 题目 给的是前序遍历的结果，我们也需要用前序遍历的方式来构建。
解题步骤
程序框架
creationTree 方法 【构造二叉树】
思路： 创建一个静态变量 i ，用来遍历字符串，辅助我们去构造 一个 二叉树。
不要抱有太大的异或，你就跟着我的思路一步步来。稳得很！
因为我们不知道这个字符串具体输入什么样的数据。所以重点就在于判断！
判断 我们拿到的字符串数据。
代码 如下
importjava.util.*;// 树节点classTreeNode{publicchar val;publicTreeNode left;publicTreeNode right;publicTreeNode(char val){this.val = val;}}publicclassMain{publicstaticvoidmain(String[] args){// 循环输入Scanner sc =newScanner(System.in);while(sc.hasNextLine()){String str = sc.nextLine();//读取 字符串TreeNode root =creationTree(str);// 构造二叉树返回其根结点inorderTraversal(root);// 中序遍历打印}
sc.close();}// 构造二叉树publicstaticint i =0;publicstaticTreeNodecreationTree(String str){TreeNode root =null;// 先定义 一个为nullchar ch = str.charAt(i);// 获取下标为 i 的 字符 数据if( ch !='#'){// ch 为字符数据时
root =newTreeNode(ch);// root 根据 ch 去创建一个节点
i++;// 为下一次获取 字符 数据，做准备。
root.left =creationTree(str);// 宏观：将 左子树接回根结点
root.right =creationTree(str);// 宏观：将 右子树接回根结点}else{// ch 为 ‘#’ 字符时，代表空树【也就是null 节点】
i++;// 不用管，直接加加。}// 如果 ch == ‘#’，刚好 我们 root 就是 null// 如果 ch 是 字符数据，不用担心，if语句帮我们处理好了。return root;}// 中序遍历【这个简单，我就先写了】publicstaticvoidinorderTraversal(TreeNode root){if(root ==null){return;}inorderTraversal(root.left);System.out.print(root.val +" ");inorderTraversal(root.right);}}
;
LeetCode - 102. 二叉树的层序遍历
解题思维
这里我们需要 了解/实现 一下 层序遍历的代码。
思维： 跟前面判断 完全二叉树的方法一致：用队列实现。出队的时候，随便打印一下，不同的是 如果左右子树为空树，就不用入队了。【没有值可以打印】
代码如下【不是题目的最终答案 - 过渡】
代码 如下 - 这是真货
因为题目很gou！要求的 返回值，很那啥。
把 每一层的节点数据，先存入一个 线性表 中。
然后，根据层次顺序，存入 另一个线性表中。【你可以理解为 是 一个 二维数组】
但是，有一个问题：我们前面写的 层序遍历，是没有分层的。
只要出队的元素不为null，我就打印一下。
来下面的代码，看看我是怎么处理的
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicList<List<Integer>>levelOrder(TreeNode root){List<List<Integer>> result =newArrayList<>();if(root ==null){return result;}Queue<TreeNode> q =newLinkedList<>();
q.offer(root);while(!q.isEmpty()){int size = q.size();// 记录当前队列的元素个数List<Integer> list =newArrayList<>();// 存储当前层次的元素while(size >0){// 将当前层次的元素 出队TreeNode tmp = q.poll();// 出队
list.add(tmp.val);// 存入 list 中
size--;// 表示 将当前层次的元素存入完成。// 同时，将该层次节点 的 下一层次的节点（左右子树） 存入if(tmp.left !=null){
q.offer(tmp.left);}if(tmp.right !=null){
q.offer(tmp.right);}}
result.add(list);// 将每层的 list 存入 result 中}// 返回 结果return result;}}
代码 解析
;
LeetCode - 236. 二叉树的最近公共祖先
;
题目解析
给我们一棵二叉树，和 这棵二叉树中的两个节点，要求我们找到 这两个节点的 公共祖先【父亲节点，注意父亲节点也可以是 二个节点中的一个。也就是说另一个节点是孩子结点】
;
解题思维
;
思维一：假设题目给定的是一棵二叉搜索树
;
代码如下 - 【二叉搜索树得出的某些结论，同样适用于本题】
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/classSolution{publicTreeNodelowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){// 终止条件if(root ==null){return root;}// 根结点为 p 和 q 中一个if(root == q || root == p){return root == q ? q : p;}// 在 左子树中 寻找 p 和 q 中的一员 或者 公共祖先【可能没有找到：null】// 宏观：在左子树中 p 和 q 的公共祖先TreeNode leftNode =lowestCommonAncestor(root.left,p,q);// 在 右子树中 寻找 p 和 q中的一员 或者 公共祖先【可能没有找到：null】// 宏观：在右子树中 p 和 q 的公共祖先TreeNode rightNode =lowestCommonAncestor(root.right,p,q);// 如果在 root 的 左右子树寻找结果都不为null，说明 p 和 q 处于不同的子树当中if(leftNode !=null&& rightNode !=null){return root;// 那么此时的根结点就是 公共祖先}// 如果在 root 的 左右子树寻找结果，有一个结果为null，说明 p 和 q 处于相同同的子树当中// 那么就有可能出现 p 是 q 的 公共祖先，或者 q 是 p 的公共祖先。// 在根据递归的性质：每个节点都扮演过根结点的角色// 所以，在 p 或 q 的公共祖先的情况下：root 递归到 到这个位置,就会直接返回 root.// 再从宏观出发： p 和 q 还有 它们的公共祖先，在一棵子树下// 很显然：另一棵子树 是不可能找到公共祖先节点的，所以 root 会递归到 null，并将其作为结果返回。// 我们只需去判断一棵子树的结果就够了。return leftNode ==null? rightNode : leftNode;}}
;
代码附图
如果根结点不为公共节点，就去 左右子树中 去找。
如果 根结点 就是 p 和 q 的一员，直接返回根结点。
需要注意的是：有可能 p 和 q 都在 左子树中；或者，都在右子树中。
且，可能存在 p 是 q 的 祖先节点的情况，或者， q 是 p 的 祖先节点情况。；
思维二 - 假设 这个二叉树使用的是孩子双亲表示法来来表示
代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/classSolution{publicTreeNodelowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){if(root ==null){return root;}Stack<TreeNode> stackq =newStack<>();Stack<TreeNode> stackp =newStack<>();// 获取路径getPath(root,p,stackp);getPath(root,q,stackq);// 获取栈的大小int sizep = stackp.size();int sizeq = stackq.size();// 利用快慢指针的思想，让栈大的一方先出栈// 直到两个栈的大小一致。然后，一起出栈// 如果 出栈的元素 相等，此元素就是 最近祖先节点int difference = sizep - sizeq;if(difference <0){
difference = sizeq - sizep;while(difference>0){
stackq.pop();
difference--;}while(!stackq.isEmpty()&&!stackp.isEmpty()){TreeNode nodeq = stackq.pop();TreeNode nodep = stackp.pop();if(nodeq == nodep){return nodep;}}}else{while(difference>0){
stackp.pop();
difference--;}while(!stackq.isEmpty()&&!stackp.isEmpty()){TreeNode nodeq = stackq.pop();TreeNode nodep = stackp.pop();if(nodeq == nodep){return nodep;}}}// 表示 这个二叉树 不存在 祖先节点returnnull;}// 获取 指定节点 的 存储路径publicbooleangetPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){if(root ==null|| node ==null){returnfalse;}
stack.push(root);if(root == node){returntrue;}boolean flag =getPath(root.left,node,stack);if(flag){returntrue;}
flag =getPath(root.right,node,stack);if(flag){returntrue;}
stack.pop();returnfalse;}}
牛客题霸 - JZ36 二叉搜索树与双向链表
题目解析
将一颗搜索二叉树，进行有序排序【升序】。按照升序的顺序，创建一个链表【双向】。
解题思维
首先通过上面那题思维一，我们得知 搜索二叉树，如果对其进行中序遍历，其结果就是有序的。
最后一个问题： 将其结果转换成一个双向链表 【难点】
代码如下
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/publicclassSolution{publicTreeNodeConvert(TreeNode pRootOfTree){if(pRootOfTree ==null){returnnull;}// 获取 头节点位置 - 详尽见附图inorderTraversal(pRootOfTree);TreeNode head = pRootOfTree;while(head.left !=null){
head = head.left;}return head;}publicTreeNode prev ;publicvoidinorderTraversal(TreeNode root){if(root ==null){return;}inorderTraversal(root.left);// 打印
root.left = prev;if(prev !=null){
prev.right = root;}
prev = root;// System.out.print(root.val + " ");inorderTraversal(root.right);}}
附图
LeetCode - 105. 从前序与中序遍历序列构造二叉树
这题的意思，就不用我讲了。跟前面的那道选择题一样【根据 两种遍历方法（前中 或 中后）确定 一棵唯一的二叉树】，不同的是 选择要求返回 另外一种遍历的结果，而这题要我们返回 这棵二叉树的根结点。相同的是 根据两种遍历方式 确定 / 构造 唯一 的 二叉树。
解题思维
根据上面的附图，从而引申出我的解题逻辑。
代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicTreeNodebuildTree(int[] preorder,int[] inorder){// 根据 一种遍历结果是无法确定一棵唯一的二叉树的。if(preorder ==null|| inorder ==null){returnnull;}returncreationTree(preorder,inorder,0,inorder.length -1);}publicint rootIndex;// 遍历前序数组的变量，默认值为 0publicTreeNodecreationTree(int[] preorder,int[] inorder,int begin,int end){if(begin > end){returnnull;}TreeNode root =newTreeNode(preorder[rootIndex]);int inorderIndex =findIndex(inorder,begin,end,root.val);if(inorderIndex ==-1){returnnull;}
rootIndex++;
root.left =creationTree(preorder,inorder,begin,inorderIndex-1);
root.right =creationTree(preorder,inorder,inorderIndex+1,end);return root;}privateintfindIndex(int[] inorder,int begin,int end,int key){for(int i = begin;i <= end;i++){if(key == inorder[i]){return i;}}return-1;}}
LeetCode - 106. 从中序与后序遍历序列构造二叉树
这个就很简单了，就是上面那题改一些地方就行了。
preorder 换成 postorder，rootIndex 要赋值 【postorder.length - 1】
因为 后序遍历: 左 》 右 》根，也就是说：倒数第一个元素 是 根结点，倒数第二个 是 右子树的根结点。【也就是说，先创建 根结点，其次是 右子树，最后左子树】
代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicint rootIndex;// 遍历前序数组的变量，默认值为 0publicTreeNodebuildTree(int[] inorder,int[] postorder){// 根据 一种遍历结果是无法确定一棵唯一的二叉树的。if(postorder ==null|| inorder ==null){returnnull;}
rootIndex = postorder.length -1;returncreationTree(postorder,inorder,0,inorder.length -1);}publicTreeNodecreationTree(int[] postorder,int[] inorder,int begin,int end){if(begin > end){returnnull;}TreeNode root =newTreeNode(postorder[rootIndex]);int inorderIndex =findIndex(inorder,begin,end,root.val);if(inorderIndex ==-1){returnnull;}
rootIndex--;
root.right =creationTree(postorder,inorder,inorderIndex+1,end);
root.left =creationTree(postorder,inorder,begin,inorderIndex-1);return root;}privateintfindIndex(int[] inorder,int begin,int end,int key){for(int i = begin;i <= end;i++){if(key == inorder[i]){return i;}}return-1;}}
LeetCode - 606. 根据二叉树创建字符串
题目解析
题目大概的意思：将一个二叉树转换成一个由括号和整数组成的字符串。
代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicStringtree2str(TreeNode root){if(root ==null){return"()";}StringBuilder sb =newStringBuilder();preOrderChange(root,sb);return sb.toString();}publicvoidpreOrderChange(TreeNode root,StringBuilder sb ){if(root ==null){return;}
sb.append(root.val);if(root.left !=null){
sb.append("(");preOrderChange(root.left,sb);
sb.append(")");}else{// root.left == null;if(root.right ==null){return;}else{
sb.append("()");}}if( root.right ==null){return;}else{
sb.append("(");preOrderChange(root.right,sb);
sb.append(")");}}}
拓展题
LeetCode - 144. 二叉树的前序遍历 - 非递归实现
解题思维 —— 借助栈
代码如下
// 非递归classSolution{publicList<Integer>preorderTraversal(TreeNode root){List<Integer> list =newArrayList();Stack<TreeNode> stack =newStack<>();TreeNode cur = root;while(cur !=null||!stack.isEmpty()){while(cur!=null){
list.add(cur.val);
stack.push(cur);
cur = cur.left;}TreeNode tmp = stack.pop();
cur = tmp.right;}return list;}}
LeetCode - 94. 二叉树的中序遍历 - 非递归
有了前序之见。那么，中序将不存在问题。无非就是 list.add 语句换个位置。
代码如下
// 非递归classSolution{publicList<Integer>inorderTraversal(TreeNode root){List<Integer> list =newArrayList<>();Stack<TreeNode> stack =newStack<>();TreeNode cur = root;while(cur !=null||!stack.isEmpty()){while(cur!=null){
stack.push(cur);
cur = cur.left;}TreeNode tmp = stack.pop();
list.add(tmp.val);
cur = tmp.right;}return list;}}
LeetCode - 145. 二叉树的后序遍历- 非递归
代码如下
// 非递归classSolution{publicList<Integer>postorderTraversal(TreeNode root){List<Integer> list =newArrayList<>();Stack<TreeNode> stack =newStack<>();TreeNode cur = root;TreeNode prev =null;// 见附图while(cur !=null||!stack.isEmpty()){while(cur!=null){
stack.push(cur);
cur = cur.left;}TreeNode tmp = stack.peek();if(tmp.right ==null|| prev == tmp.right){// 见附图
stack.pop();
list.add(tmp.val);
prev = tmp;}else{
cur = tmp.right;}}return list;}}
附图
本文结束
版权归原作者 Dark And Grey 所有， 如有侵权，请联系我们删除。