【Java】二叉树入门详解（包含二叉树0J练习解析）

目录

一、 树型结构（了解）

1.1 概念

要想学习二叉树，你要知道什么是 树

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。

把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 有一个特殊的节点，称为根节点，根节点没有前驱节点
• 除根节点外，其余节点被分成M(M > 0)个互不相交的集合T1、T2、…、Tm，其中每一个集合 Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有0个或多个后继
• 树是递归定义的

看一下不是树：

---

1.2 概念（重要）

节点的度： 一个节点含有的子树的个数称为该节点的度； 如上图：A的为6

D的度是1 ,E的度是2…

---

树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

A是最大的结点，除了A没有更大的了，所以是6；

---

叶子节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点

---

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

---

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

---

根结点：一棵树中，没有双亲结点的结点；如上图：A

---

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

这里是4层

---

树的深度：相对于结点的 树中节点的最大层次

树的高度：最大的深度就是高度

---

非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点

---

兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：I、J是兄弟节点

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

---

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

---

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

---

森林：由m（m>=0）棵互不相交的树的集合称为森林(一棵树叫树 两棵树以上叫森林)

---

1.3 树的表示形式（了解）

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，

孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的 孩子兄弟表示法。

classNode{//里面有的属性int value;// 树中存储的数据Node firstChild;// 第一个孩子引用  Node nextBrother;// 下一个兄弟引用}

图片示例：A的孩子是B ，A没有兄弟结点(null)，B的兄弟结点是C…

1.4 树的应用

树的应用我们经历过许多了，比如下面的：

都是一层一层的关系 了解即可

---

二、 二叉树的认识（重点）

2.1 概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

二叉树的特点：

1. 每个结点最多有两棵子树，即二叉树不存在度大于 2 的结点。
2. 二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树。

2.2 二叉树的基本形态

上图给出了几种特殊的二叉树形态，从左往右依次是：空树、只有根节点的二叉树、节点只有左子树、节点只有右子树、节点的左右子树均存在，一般二叉树都是由上述基本形态结合而形成的。

2.3 两种特殊的二叉树

1. 满二叉树: 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为2^k-1，且结点总数是 ，则它就是满二叉树。
2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树

来看满二叉树 K是4 ，2的4次方-1， 是15，满二叉树刚刚好15个结点，也就是说 每一层都放满的情况下，那么就是满二叉树。

什么叫做完全二叉树呢？？ 每一次从左往右依次存放
那么不是完全二叉树是怎么样的呢？

可以看见就断了 ，注意这些数字是从左边往右边放的，一旦有间隙就不是完全二叉树了。

满二叉树也是一颗特殊的完全二插数。

---

2.4 二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) (i>0)个结点
2. 若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^(k-1) (k>=0)

比如现在深度是4 2^k-1 == 16 -15 个结点

1. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

上面叶节点8个 非叶节点7个 8=7+1；

1. 具有n个结点的完全二叉树的深度k为log2（n+1） 上取整
2. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

• 若i>0，双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点 (求父亲节点的下标)

(5-1)/2 = 2

• 若2i+1<n，左孩子序号：2i+1，否则无左孩子（求左孩子）
• 若2i+2<n，右孩子序号：2i+2，否则无右孩子（求右孩子）

---

2.5 二叉树的存储

二叉树的存储结构分为：顺序存储 和 类似于链表的链式存储。

二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：

// 孩子表示法classNode{int val;// 数据域Node left;// 左孩子的引用，常常代表左孩子为根的整棵左子树Node right;// 右孩子的引用，常常代表右孩子为根的整棵右子树}// 孩子双亲表示法classNode{int val;// 数据域Node left;// 左孩子的引用，常常代表左孩子为根的整棵左子树Node right;// 右孩子的引用，常常代表右孩子为根的整棵右子树Node parent;// 当前节点的根节点}

孩子双亲表示法后序在平衡树位置介绍，本文采用 孩子表示法 来构建二叉树。

---

2.6 二叉树的基本操作

2.6.1 二叉树的遍历.

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。

访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础

---

所以说各位 二叉树的遍历是最基础了，希望大家要好好来看哦~~

在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱,

---

如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：

1. NLR：前序遍历(Preorder Traversal 亦称先序遍历)——>访问根结点—>根的左子树—>根的右子树。
2. LNR：中序遍历(Inorder Traversal)——>根的左子树—>根节点—>根的右子树。
3. LRN：后序遍历(Postorder Traversal)——>根的左子树—>根的右子树—>根节点

这里不需要记，如果实在不知道可以看N在什么地方，N在前就是，前序遍历，在最右就是右序遍历 …。

---

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

前序遍历流程图：按照箭头编号来 ： 根-》左-》右

遇见NULL 返回

前序遍历注意一点，遇见根打印，根打印完，先去左边，在去右边

最后前序遍历的结果是：ABCEF

---

中序遍历流程图：按照箭头编号来

遇见NULL 返回

中序遍历注意一点，遇见最左打印，根在打印，最后去打印右边

顺序和前序一样，只是打印时机不一样而已

最后结果：DBAECF

---

后序遍历流程图：按照箭头编号来

遇见NULL 返回

后序遍历注意一点，左和右都没有在打印根，先把左走完，然后在右走完，最后打印根

最后结果是:DBEFCA

结论不管是前中后遍历，遍历路径是一样的，只是访问时机不一样。

---

写一个题目大家试一试看看上面学的怎么样：

答案在下：

前序：根左右 ABDEHCFG
中序：左根右DBEHAFCG
后序：左右根DHEBFGCA

大家可以看一下和你的答案是否相同，需要注意的是中序的E，其实这个E也是一个根节点，只是左为空了。

2.6.2 二叉树的基本操作

我们要准备使用代码创建二叉树了，采用一种穷举式创建，实际上，一会儿创建二叉树的代码，不是最后的创建方式，只是一个举例说明。

下面来看代码：

classNode{publicchar val;//值publicNode left;//左树publicNode right;//右树publicNode(char val){this.val = val;}}publicclassTestBinaryTree{/*
    * 使用穷举的方式创建一颗二叉树
    * */publicvoidcreateTree(){NodeA=newNode('A');NodeB=newNode('B');NodeC=newNode('C');NodeD=newNode('D');NodeE=newNode('E');NodeF=newNode('F');NodeG=newNode('G');NodeH=newNode('H');}}

我们需要创建的树是这个样子的：

那么在代码里面就是这样创建的：

publicclassTestBinaryTree{/*
    * 使用穷举的方式创建一颗二叉树
    * */publicNodecreateTree(){//返回的格式是Node类型的NodeA=newNode('A');NodeB=newNode('B');NodeC=newNode('C');NodeD=newNode('D');NodeE=newNode('E');NodeF=newNode('F');NodeG=newNode('G');NodeH=newNode('H');A.left =B;A.right =C;B.left =D;B.right =E;C.left =F;C.right=G;E.right =H;returnA;//返回根节点}}

接下来我们来看一下要实现的操作：

（1）前序遍历

voidpreOrderTraversal(Node root){//前序遍历if(root==null){return;}System.out.println(root.val+" ");preOrderTraversal(root.left);preOrderTraversal(root.right);}

上面的代码是不是看起来很简单呢？

讲一下具体的思想吧：因为是前序遍历所以顺序是

根->左->右

，首先我们判断的是root等于null吗？如果不等于null，我们就打印这个根的值，然后把当然节点的左树给他：

现在可以看见代码是不是用调用了一次函数

然后继续判断下一个左树是不是空：

不是空继续下去，又是一个函数

这里等于空了 return了 ，返回上一个D的那个节点对吧

那么D 的左走完了，是不是要走D的右边了呢？？

有人不明白，为什么是D的右，因为上面代码是这样的左的的递归函数return就出来了，然后在到右边，右边如果也出来的话，那就是返回到B，B的left树等于null，就会去B的right树，所以这样递归每一个节点的左右都会被打印到！！！
这就是前序遍历，下面来看一下代码正常不：

publicclassTestDemo{publicstaticvoidmain(String[] args){TestBinaryTree testBinaryTree =newTestBinaryTree();Node root = testBinaryTree.createTree();//创建一个树
        testBinaryTree.preOrderTraversal(root);//把树使用这个方法}}

结果： A B D E H C F G

结果和我们上面手动的对比一下发现结果也是一样的：

---

（2）中序遍历

// 中序遍历voidinOrderTraversal(Node root){if(root ==null){return;}inOrderTraversal(root.left);System.out.print(root.val+" ");inOrderTraversal(root.right);}

讲一下思路吧：中序遍历是

左->根->右

来看一下代码：

如果不是null把b传下来

然后继续传：

然后在传：

root是空了，结束这个 返回上一层的D：

然后就开始走这步，也就是打印D

然后D的右是null，然后就到花括号，说明D全部结束，开始走B节点的左右，依次，所以就是中序遍历。

这种就是子问题思路：就是大问题化子问题。

看看结果：

和手动的结果:一模一样

---

（3）后序遍历

// 后序遍历voidpostOrderTraversal(Node root){if(root ==null){return;}postOrderTraversal(root.left);postOrderTraversal(root.right);System.out.print(root.val+" ");}

讲一下思路吧：
假设root已经是D了

他的左右是不是null，所以我们可以执行第三步代码：打印D

然后返回到B，刚刚B的左边，也就是D已经结束啦，现在我们要去B的第二个代码

就是到了E，但是E的左是null，返回上来就去了E的第二个代码，也就是去了H

到H之后左右都是null，执行H的第三个代码：

打印H，然后返回上一层打印E，

以上就是大概流程了

结果：

---

(4)遍历思路-求结点个数

// 遍历思路-求结点个数staticint size =0;voidgetSize1(Node root){if(root==null){return;}
        size++;getSize1(root.left);getSize1(root.right);}

思路这个很简单：每次不为空调用的时候size加1

---

(5.)子问题思路-求结点个数

intgetSize2(Node root){if(root==null){return0;}returngetSize2(root.left)+getSize2(root.right)+1;}

思路解析：这个字问题解决的根本原理是，左边节点个数，加上右边节点个数，每进去一次函数就会去查看左右节点有没有，只要进去一次后面那个加1就会生效，就到达了计数的效果。

---

(6)遍历思路-求叶子结点个数

staticint leafSize =0;voidgetLeafSize1(Node root){if(root==null){return;}if(root.left==null&&root.right==null){
            leafSize++;}getLeafSize1(root.left);getLeafSize1(root.right);}

思路解析：通过遍历的方式，叶子节点指的是左，右节点都没有（看下面的DHFG），这里是判断一下改节点的左右是不是没有，递归传下去，遍历了左，右节点，每到一个节点就要判断是不是叶子节点.

---

(7)子问题思路-求叶子结点个数

intgetLeafSize2(Node root){if(root==null){return0;}if(root.left==null&&root.right==null){return1;}returngetLeafSize2(root.left)+getSize2(root.right);}

思路：也就是左边的叶子节点，和右边的叶子节点相加，每一次产生了一个新的函数就会去判断一下是不是叶子节点，如果是上面return1，当left走完，就去右边去，依次递归下去；

来个图片的思路：

假设我们到了最后一个节点就是root是D

这个时候执行判断的代码并且return1；

现在B返回的是1

然后是不是接下来执行E节点，E的结点left是null，但是右树不是，所以我们去到了H树。

H满足叶节点的所以执行下面代码 返回1

就这样依次相加，即可完成

---

(8)子问题思路-求第 k 层结点个数

intgetKLevelSize(Node root,int k){if(root  ==null){return0;}if(k==1){return1;}returngetKLevelSize(root.left,k-1)+getKLevelSize(root.right,k-1);}

思路：假设我们k是3 ，要求第三层节点个数，那么以子问题来看，相当于是要找出A的左树的第二层，和右树的第二层， 所以我们可以得出 我们要想解出，这个题，只需要找到左树的第k-1层，和右树的第k-1层，当k=1的时候就是就已经是第k层了，这个时候左右树节点相加，即可求出。

---

(9)获取二叉树的高度

intgetHeight(Node root){if(root==null){return0;}int leftHeight =getHeight(root.left);int rightHeight =getHeight(root.right );returnMath.max(leftHeight,rightHeight)+1;//当前节点的大小}intgetHeight(Node root){if(root==null){return0;}int leftHeight =getHeight(root.left);int rightHeight =getHeight(root.right );return leftHeight>rightHeight?leftHeight+1:rightHeight+1;}

思路：分别找左数的高度和右树的高度，可以看见代码上最后有一个加1，如果最后一个树走完，就会加1 ，最后在最大值加1就是数的高度。

第二个代码就是哪边大就哪边加1。

---

(10) 查找 val 所在结点，没有找到返回 null

Nodefind(Node root,char val){if(root ==null){returnnull;}if(root.val ==val){return root;}Node ret =find(root.left,val);if(ret!=null){return ret;//左边找到了}
         ret =find(root.right  ,val);return ret;}

思路：先看一下根是不是当前找的值，在查找左边的所有的树节点，如果不为了null，就是找到了，如果没有找到，在去找右边，没有找到返回null，就结束了。

---

2.7 基础面试题力扣

1. 二叉树的前序遍历。

力扣链接

classSolution{List<Integer> list =newArrayList<>();publicList<Integer>preorderTraversal(TreeNode root){if(root==null){return list;}
        list.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return list;}}

思路：这里给定的是一个List< Integer >类型，所以我们需要一个list来装起来，先判断是否是null，如果是null返回该ist，注意每次递归会产生新的list值需要保存起来，如果没有保存起来，建议写变成我那样。

---

2. 二叉树的中序遍历。

在线OJ

classSolution{List<Integer> list =newArrayList<>();publicList<Integer>inorderTraversal(TreeNode root){if(root==null){return list;}inorderTraversal(root.left);
            list.add(root.val);inorderTraversal(root.right);return list;}}

中序和前序一样，需要注意中序是左根右

---

3. 二叉树的后序遍历。

在线OJ

classSolution{List<Integer> list =newArrayList<>();publicList<Integer>postorderTraversal(TreeNode root){if(root==null){return list;}postorderTraversal(root.left);postorderTraversal(root.right);
        list.add(root.val);return list;}}

后序和中序一样，需要注意后序是左右根

---

4. 二叉树的后序遍历。

在线OJ
题目

classSolution{publicbooleanisSameTree(TreeNode p,TreeNode q){if(p==null&& q!=null|| q==null&&p!=null){//判断有没有节点是nullreturnfalse;}if(p==null&&q==null||q==null&&p==null){//判断节点是否全部为空returntrue;}if(q.val!=p.val){//判断值一不一样returnfalse;}returnisSameTree(p.left,q.left)&&isSameTree(p.right,q.right);//递归所有的左树和右树}}

解题思路：要看这两颗树是否相同，要根据从结构和值，依次遍历判断，下面的图片展示出2颗树的不同之处，和一样之处

---

5. 另一颗树的子树。

在线OJ
题目：

classSolution{publicbooleanisSametree(TreeNode root,TreeNode subRoot){if(root!=null&& subRoot==null|| subRoot!=null&& root==null){returnfalse;}if(root==null&& subRoot==null){returntrue;}if(root.val!=subRoot.val){returnfalse;}returnisSametree(root.left,subRoot.left)&&isSametree(root.right,subRoot.right);}publicbooleanisSubtree(TreeNode root,TreeNode subRoot){if(root==null|| subRoot ==null){returnfalse;}if(isSametree(root,subRoot)){returntrue;}if(isSubtree(root.left,subRoot)){returntrue;}if(isSubtree(root.right,subRoot)){returntrue;}returnfalse;}}

思路:要想解决这个问题，我们可以使用到上一个的题目解答来帮助解决问题，上面的题目也是判断2个树是否相等，在此题可能发生的条件中：

所以我们通过递归的方式，判断该树的左和右边是否一样，把isSametree写在前面，让这个函数先去判断字符是否包含，要注意2颗数为null。

---

6. 判断一颗二叉树是否是平衡二叉树。

题目：

classSolution{publicintgetHeight(TreeNode root){if(root==null){return0;}int leftHeight =getHeight(root.left);int rightHeight =getHeight(root.right );if(leftHeight>=0&& rightHeight>=0&&Math.abs(leftHeight-rightHeight)<=1){returnMath.max(leftHeight,rightHeight)+1;}else{return-1;}}publicbooleanisBalanced(TreeNode root){returngetHeight(root)>=0;}}

思路：从树下往上面求子树的高度是多少，如果左右子树的高度的绝对值大于1，那么证明不是一个平衡二叉树，返回一个负1

---

7. 对称二叉树。

在线OJ

classSolution{publicbooleanisSymmetricChild(TreeNode leftTree ,TreeNode rightTree){if(leftTree==null&& rightTree ==null){//证明是空树returntrue;}if(leftTree==null&&rightTree!=null||leftTree!=null&&rightTree==null){returnfalse;}if(leftTree.val!=rightTree.val){returnfalse;}returnisSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);}publicbooleanisSymmetric(TreeNode root){if(root==null){returnfalse;}returnisSymmetricChild(root.left ,root.right);}}

思路：找出可能不是对称二叉树的关系有点像找二叉树子树，

1.leftTree或者rightTree为空

2.leftTree和rightTree的值不一样

最后如果是对称的那么要上面的条件避免

还需要leftTree的左子树和rightTree的右子树一样并且leftTree的右树和rightTree的左树一样

---

2.8 二叉树的层序遍历

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历我们可以使用队列来实现大概是下面这样的：队列（先进先出）

来使用代码模拟实现一下：

classNode{publicchar val;//值publicNode left;//左树publicNode right;//右树publicNode(char val){this.val = val;}}publicvoidlevelOrderTraversal(Node root){if(root==null){return;}Queue<Node> queue =newLinkedList<>();
        queue.offer(root);//放入while(!queue.isEmpty()){//队列不是空的时候进入  弹完结束Node top = queue.poll();//弹出元素System.out.println(top.val+" ");//打印元素if(top.left!=null){//判断那个节点左是不是空的 
                queue.offer(top.left);//放入元素}if(top.right!=null){//判断那个节点右是不是空的 
                queue.offer(top.right);//放入元素}}}

结果:

---

2.9 进阶面试题

1. 二叉树的分层遍历

在线OJ

答案：

classSolution{publicList<List<Integer>>levelOrder(TreeNode root){List<List<Integer>> ret =newArrayList<>();//创建一个大集合if(root==null){return ret;}Queue<TreeNode> queue =newLinkedList();//创建一个队列
            queue.offer(root);//放入元素while(!queue.isEmpty()){//队列不为空进入int size =queue.size();//看当前队列有几个元素List<Integer> list =newArrayList<>();//存放，每一层的数据while(size>0){TreeNode top = queue.poll();
                    list.add(top.val);if(top.left!=null){         
                    queue.offer(top.left);//放入元素}if(top.right!=null){
                        queue.offer(top.right);}
                    size--;//每弹出一个元素size--}
                ret.add(list);//把list添加到ret里面去}return  ret;}}

思路：从这个题目可以发现是一个list里面还有一个list ，使用队列层序遍历，每放一个元素记录它的大小，创建一个新的list存放将要弹出的元素，最后把新list添加到ret这个数组里面

---

2. 判断一棵树是不是完全二叉树

booleanisCompleteTree(Node root){if(root==null){returntrue;}Queue<Node> queue =newLinkedList<>();
        queue.offer(root);//放入while(!queue.isEmpty()){//如果队列不是空进入Node top = queue.poll();//把要弹出的元素保存下来if(top==null){//如果最后是null了break;//跳出循环}
            queue.offer(top.left);//把左树的元素放下来
            queue.offer(top.right);//把右边的元素放下来}while(!queue.isEmpty()){Node top = queue.peek();//检查队列里面是否有 元素if(top!=null){//还有元素证明不是完全二叉树returnfalse;}
            queue.poll();//把null全部弹出}returntrue;//证明是完全二叉树}

思路：我们知道完全二叉树是这样的

我们可以使用分层遍历，使用队列来看,如果完全二叉树,队列里面都是空的

但是其实像最后的结点后面都是有一个null的，我们可以使用这个null来判断里面是否还有元素，如果还有元素则不是完全二叉树，像下面这样就不是完全二叉树。

---

3. 二叉树的构建及遍历

在线OJ

首先我们来看一下题目的意思吧：前序遍历，空格字符代表空树 ,差不多就是下面这个图

思路：ACM模式下代码都是自己手动输入，比较容易打错字，需要注意，本题关键是怎么创建二叉树，下面代码使用循环，前序遍历，然后写了个中序遍历输出的方法，最后遍历即可

importjava.util.*;//创建二叉树节点 返回nodeclassTreeNode{publicchar val;publicTreeNode left;publicTreeNode right;publicTreeNode(char val){//构造 方法this.val = val;}}publicclassMain{publicstaticint  i =0;//创建二叉树publicstaticTreeNodecreateTree(String  str){TreeNode root =null;if(str.charAt(i)!='#'){//如果不是空格
            root  =newTreeNode( str.charAt(i));
            i++;
            root.left =createTree(str);
            root.right =createTree(str);}else{
            i++;}return root;}//最后结果输出中序遍历的结果//中序遍历publicstaticvoidinorder(TreeNode root){if(root ==null){//如果节点为空return;}inorder(root.left);System.out.print(root.val +" ");inorder(root.right);}publicstaticvoidmain(String[] args){Scanner scan =newScanner(System.in);String str =scan.nextLine();//遇到空格不停止TreeNode root =createTree(str);inorder(root);//中序遍历输出}}

---

4. 查找二叉树公共祖先

在线oj

先搞清楚什么是公祖先:

p在5，q在8 ，他们相交的地方是3，3就是公共祖先

在举一个列子：

这个是5是公共结点

解题思路：
经过上面的图发现出现2个情况：

  第一个是P 和Q 在根节点的 左边 和右边
  
  
   第二个是P 和Q 其中有一个是根节点

可能发生这样的事情：
root就是其中的一个 p 或者 q

root.left 是空 ，或者root.right是空

或者都不是空

因为要一个个找我们使用到递归 可能发生的情况如下

publicTreeNodelowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){if(root ==null)returnnull;//空树没有公共祖先if(root==p || root == q){return root;}//递归TreeNode leftTree =lowestCommonAncestor(root.left,p,q);TreeNode rightTree =lowestCommonAncestor(root.right,p,q);if(leftTree!=null&& rightTree!=null){return root;}if(leftTree==null&& rightTree!=null){return rightTree;}if(leftTree!=null&& rightTree==null){return leftTree;}if(leftTree==null&& rightTree==null){returnnull;}returnnull;}

---

5.二叉树搜索树转换成排序双向链表

在线OJ

思路：我们要先知道什么是二叉搜索树

在把二叉树变成双向链表我们要知道双向链表的域

有prev 和 next域

知道了这些 我们来看一下怎么把 排好序这个问题解决

其实二叉搜索树 使用中序遍历就会变成有序的:比如上面的那颗树，中序遍历就是有序的了。

那么怎么搞一个双向链表出来呢；

我们可以看见二叉树其实要是三个域

让左成为前驱，让右成为后继

画一下 绿色是前驱，红色是后驱

4的前驱是null 4的后驱是6 ，6的前驱是 4 ，6的后继是8 只需要看做拉平

建议对着图写代码

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/publicclassSolution{TreeNode prev =null;//定义在外面 publicvoidConvertChild(TreeNode pCur){if(pCur ==null){return;}ConvertChild(pCur.left);
         
          pCur.left = prev;if(prev!=null){
             prev.right = pCur;}
         prev  = pCur;ConvertChild(pCur.right);}publicTreeNodeConvert(TreeNode pRootOfTree){if(pRootOfTree ==null){returnnull;}ConvertChild(pRootOfTree);TreeNode head = pRootOfTree;while(head.left !=null){ 
            head = head.left;//找头节点}return head;}}

---

6.根据一棵树的前序遍历与中序遍历构造二叉树

在线OJ

在此之前我们先来做一个题：

思路：我们可以根据前序遍历知道根在哪里，在根据中序知道根的左右树，最后就得到了下面的这样图：

那么后序遍历就是：左右根

问:

不可以：原因如下

那么开始来做题，我们根据前序的方式来做题：

2个数组 我们根据前序遍历找到根，然后在去中序遍历找到前序遍历的那个根，然后树的 左树，和右树也使用递归来找，只是找到区间范围可以根据根所在的位置有个范围；