【数据结构_10】二叉树（2）

一、根据树的遍历效果还原树
紧接着（1），我们继承来讨论：如果给了树的遍历效果，我们可否把这个树给还原出来呢？
如果只给一种遍历效果，那么我们无法对树进行还原。
只有给了我们先序+中序，或者后序+中序这两种情况的遍历效果，我们才可以得到树的效果。 
*这里不考虑层序的题目，如许的题目是不考层序的。
（1）如果给了先序遍历和中序遍历
1.先序遍历的第一个元素就是根节点
2.在中序遍历中，左子树就在根节点左侧，右子树就在根节点右侧，拿着根节点E，在中序效果中进行查找。
（2）如果给了后序遍历和中序遍历
1.取出后序遍历的末了一个元素，那就是树的根节点
2.拿着根节点在中序中进行查找，查找规则：在中序遍历中，左子树就在根节点左侧，右子树就在根节点右侧，拿着根节点E，在中序效果中进行查找。
3.进行左右子树的还原
*总而言之，根据前序遍历后序遍历中序遍历进行树的还原实质上仅仅是考察这三个知识点：
1.先序的第一个元素，就是根节点（后序也是雷同，末了一个元素是根节点）
2.先序中根节点左侧的内容就是左子树的中序效果，右侧内容就是右子树的中序效果
3.先序中，如果明确了根节点和子树范围，此时，子树范围对应的内容就是子树的先序效果（后序也是雷同，子树对应的内容就是子树的后序效果）
二、求树的节点个数

2.     //根据递归求树的节点个数
3.     public static int size(Node root){
4.         if(root == null){
5.             return 0;
6.         }
7.         int leftsize = size(root.left);
8.         int rightsize = size(root.right);
9.         return 1+leftsize+rightsize;
11.     }

复制代码

三、根据递归求叶子节点的个数

2.     public static int getLeafSize(Node root){
3.         if(root == null){
4.             return 0;
5.         }
7.         if(root.left == null && root.right == null){
8.             return 1;
9.         }
10.         return getLeafSize(root.left)+getLeafSize(root.right);
11.     }

复制代码

三、 求二叉树第 k 层节点的个数

2.     public static int getLevelNodeCount(int k ,Node root){
3.         //如果输入的k值小于1 或者 树为空 就返回0
4.         if(k<1 || root == null){
5.             return 0;
6.         }
7.         if(k==1){
8.             return 1;
9.         }
10.         return getLeafSize(root.right)+getLeafSize(root.left);
11.     }

复制代码

思绪：如果我们想要得到第k层节点的个数，如果k<1，这是非法的输入，如果k=1，也就是求第一层节点的个数，而非空的树第一层的节点个数也就是1。如果k>1，求第k层节点的个数，我们可以将这个题目转化为求左子树k-1层节点的个数+右子树k-1层的节点个数
四、求二叉树的高度
高度/深度也就是所要求的二叉树中，从根节点出发到恣意节点，路径的最大长度。用递归的方式来求解，也就是要求A这个树的高度= max（B的高度,C的高度）+1

2.     //求二叉树的深度
3.     public static int getHeight(Node root ){
4.         if(root == null){
5.             return 0;
6.         }
7.         return 1+(Math.max(getHeight(root.left),getHeight(root.right)));
9.     }

复制代码

五、检测值为value的元素是否存在
存在返回val所在节点的引用，不存在就返回null。首先判定根节点是不是val，如果是，就直接返回该根节点，如果不是，继承递归在左子树中找，如果也没找到，就继承递归在右子树中进行查找。

2.     //检测值为val的元素是否存在
3.     public static Node find(Node root,String val){
4.         if(root== null){
5.             return null;
6.         }
7.         if(root.val.equals(val)){
8.             return root;
9.         }
10.         //在左子树中进行查找
11.         Node findResult = find(root.left,val);
12.         if(findResult != null){
13.             return  findResult;
14.         }
15.         return find(root.right,val);
16.     }

复制代码

如果一个类，没有重写toString，通过printlin打印的时间，就会触发Object自带的toString，此时的打印的格式：类型@哈希值