devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构练习】二叉树练习_1.在草稿纸上画出任意一棵二叉树abcde; 2.从键盘上输入该二叉树的数据值,采用先序

作者：小丑西瓜9 | 2024-03-22 18:49:37

赞

踩

1.在草稿纸上画出任意一棵二叉树abcde; 2.从键盘上输入该二叉树的数据值,采用先序

目录

1、检查两棵树是否相同

1.1、题目要求

1.2、代码思路

1.3、代码示例

1.4、复杂度分析

 2、另一棵树的子树

2.1、题目要求

 2.2、代码思路

2.3、代码示例

2.4、复杂度的计算

3、翻转二叉树

3.1、题目要求

3.2、代码思路

3.3、代码示例

4、 判断一棵二叉树是不是平衡二叉树

4.1、题目要求

4.2、代码思路 

1、时间复杂度为O(​编辑)的思路

2、时间复杂度为O(n)的思路 

4.3、代码示例 

1、时间复杂度为O(​编辑)的代码

 2、时间复杂度为O(n)的代码

4.4、时间复杂度的计算

5、 对称二叉树

5.1、题目要求

5.2、代码思路

5.3、代码示例

6、二叉树的分层遍历（考的比较多）

6.1、通过队列的思想

6.1.1、代码思路（循环思路）

6.1.2、代码示例

6.2、通过顺序表的嵌套（二维数组）和队列来实现

6.2.1、代码要求

6.2.2、代码思路 

 6.2.3、代码示例

7、创建一个二叉树

 8、二叉树的最近公共祖先

8.1、第一种方法 （递归做法）

 8.2、第二种方法：利用栈来做

9、 从前序与中序遍历序列构造二叉树

10、从中序与后序遍历序列构造二叉树

11、根据二叉树创建字符串

12、判断一个树是否为完全二叉树

12、二叉树前序遍历非递归实现 

13、二叉树中序遍历非递归实现

 14、二叉树中后续遍历非递归实现

1、检查两棵树是否相同

1.1、题目要求

给你两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。

如果两个数在结构上相同，并且结点具有相同的值，则认为他们是相同的。

示例1：

 

 示例2：

示例3：

1.2、代码思路

  • 看到判断树相同，很多同学想到的是，通过先序遍历就行，那么你错了
  • 这个问题不能使用先序遍历的思路来解决，就示例2来看，虽然遍历的结果相同，但是2结点的位置不相同，这就不能说明两棵树是相同的。
  • 要判断两棵相同，首先要看两颗树的结构相同，然后再看两棵树的每个结点所对应的值相同。
  • 结构相同的判断都有三种情况：1、两个树都不为空；2、两个树都为空；3、一棵树为空，一棵树不为空。

1.3、代码示例

  1.     public boolean isSameTree(TreeNode p,TreeNode q){
  2.         if(p == null && q == null){//1、两个数都为空，则相同
  3.             return true;
  4.         }
  5.         if(p == null && q != null || p != null && q == null){
  6.             return false;//2、两个树一棵为空，一棵不为空，则不相同
  7.         }
  8.         //3、树的结构相不相同，存在三种情况，前两种都不满足的情况下，只剩两个树都不为空的情况
  9.         //所以这里要对树的结点的值进行判断是否相同，若树中结点的值相同，则两棵树相同
  10.         if(p.val != q.val){
  11.             return false;
  12.         }
  13.         //将满足树相同的所有条件都写完之后，就通过递归遍历两棵树
  14.         //两棵树左子树和右子树都相同的情况下，返回true，否则返回false
  15.         return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
  16.     }

1.4、复杂度分析

时间复杂度：O(min(m,n))，其中m和n分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应结点都不为空是才会访问该节点，因此被访问到的结点数不会超过较小的二叉树的节点数。

空间复杂度：O(min(m,n))，其中m和n分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。

 2、另一棵树的子树

2.1、题目要求

  • 给你两棵二叉树root和subroot。检验root中是否包含和subroot具有相同结构和结点值得子树。如果存在，返回true；否则，返回false。
  • 二叉树tree的一棵子树包括tree的某个结点和这个结点的所有后代结点。tree也可以看做它自身的一棵子树。

 示例1：

 示例2：

示例3 

 2.2、代码思路

存在三种情况：

1、root树和subRoot树的结点结构相同，值相同。

2、root的左子树和subRoot节点结构相同，值相同。

3、root的右子树和subRoot节点结构相同，值相同。

2.3、代码示例

  1.     public boolean isSameTree(TreeNode p,TreeNode q){
  2.         if(p == null && q == null){
  3.             return true;
  4.         }
  5.         if(p == null && q != null || p != null && q == null){
  6.             return false;
  7.         }
  8.         if(p.val != q.val){
  9.             return false;
  10.         }
  11.         return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
  12.     }
  13. //判断一个树是否为另一个树的子树
  14.     public boolean isSubtree(TreeNode root,TreeNode subRoot) {
  15.         if(root == null ||subRoot == null){//判断两棵树是否为空，这个判断极为重要
  16.             return false;
  17.         }
  18.         if (isSameTree(root, subRoot)) {//这里调用判断两个数是否相同的方法，存在当两个树
  19. //都为空时，它会返回两个树相同，进一步说明subRoot是root的子树，但是这个方法并不会将
  20. //isSubtree方法中两树为空的条件去掉，所以要在上述添加判断两树为空条件。
  21.             return true;
  22.         }
  23.         if (isSubtree(root.left, subRoot)) {//如若不加判断两树为空的条件，则代码走到这里就可能会报空指针异常。
  24.             return true;
  25.         }
  26.         if (isSubtree(root.right, subRoot)) {
  27.             return true;//通过这个步骤找到子树，那么就返回true,否则代码就会一直递归到根节点为空的情况，那么就会返回false。
  28.         }
  29.         return false;//通过遍历没有找到，返回false
  30.     }

2.4、复杂度的计算

  • 时间复杂度：将root树设为s，subRoot树设为t。判断subRoot是否为root的子树，则要将s的每个结点，都需要和t来匹配一次，匹配一次的时间代价就是O(t），那么总时间代价就是O(s*t)。故渐近时间复杂度为s(s*t).
  • 空间复杂度：假设s深度为d_{s}，t的深度为d_{t}，任意时刻栈空间的最大使用代价是O(max{d_{s},d_{t}}). 故渐近空间复杂度为O(max{d_{s},d_{t}}).

3、翻转二叉树

3.1、题目要求

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例1

示例2

示例3

3.2、代码思路

  • 一个二叉树A的根节点为root，要翻转它的左节点和右节点，那么左节点和右节点所对应的左子树和右子树也就一次性将其翻转过来了

  • 然后再将他们的孩子结点进行翻转就实现了二叉树的翻转 

3.3、代码示例

  1.     public TreeNode invertTree(TreeNode root){
  2.         if(root == null){//首先判断二叉树的跟结点是否为空
  3.             return null;
  4.         }
  5.         //根节点不为空，则通过结点tmp将root的左树和右树进行交换
  6.         TreeNode tmp = root.left;
  7.         root.left = root.right;
  8.         root.right = tmp;
  9.         //通过递归将 整颗二叉树的左右结点都交换
  10.         invertTree(root.left);//这里不写接收返回值的引用是因为，通过代码已将子树位置交换，没有必要传给根节点。
  11.         invertTree(root.right);
  12.  
  13.         return root;//返回交换后的树
  14.     }

4、 判断一棵二叉树是不是平衡二叉树

4.1、题目要求

  • 给定一个二叉树，判断它是否是高度平衡的二叉树。
  • 本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例1

示例2

4.2、代码思路 

1、时间复杂度为O(n^{2})的思路

  • 当二叉树为空时，也是平衡的。
  • 通过求二叉树高度的方法来求每个结点的左子树和右子树的高度，进行判断是否平衡。

2、时间复杂度为O(n)的思路 

上一种方法，其中求高度的时候，出现了多次的重复计算。

  • 如果在求高度的时候将重复计算的部分优化了， 在计算结点高度的时候，如果存在那个结点不平衡的问题直接返回-1，判断二叉树不平衡。这样就大大节省了时间。也就实现了时间复杂度为O(n).
  • 当然在修改求高度的方法是，还要判断leftHeight和rightHight引用的值，若不判断两个引用的值，直接通过if（Math.abs(leftHeight - rightHeight) <= 1）判断，会产生新的问题左子树为-1，右子树为0时，最终结果就会是1.最终结果就会出错。

4.3、代码示例 

1、时间复杂度为O(n^{2})的代码

  1.     public boolean isBalanced(TreeNode root){
  2.         if(root == null){//当根节点为空时，结束。
  3.             return true;
  4.         }
  5.         int leftH = maxDepth(root.left);//通过递归，实现求出每个结点左子树的高度
  6.         int rightH = maxDepth(root.right);//通过递归，实现求出每个结点右子树的高度
  7. //当满足两个子树的高度相差1时，并且每个子树的根结点平衡时，则返回true，表示整棵树是平衡的，否则返回false，表示这颗二叉树不是平衡的。
  8.         return Math.abs(leftH - rightH) < 2 && isBalanced(root.left) && isBalanced(root.right);
  9.     }
  10.  
  11.     public int maxDepth(TreeNode root){
  12.         if(root == null){
  13.             return 0;
  14.         }
  15.         int leftHeight = maxDepth(root.left);
  16.         int rightHeight = maxDepth(root.right);
  17.         int minHeight = leftHeight>rightHeight?leftHeight:rightHeight;
  18.         return minHeight+1;
  19.     }

 2、时间复杂度为O(n)的代码

  1.     public boolean isBalanced1(TreeNode root){
  2.         return maxDepth1(root) >= 0;//这里通过调用maxDepth1方法，来判断maxDepth1方法的返回值，来确定二叉树是否平衡
  3.     }
  4.     //求根节点的长度，并且将不平衡的结点筛选出来
  5.     public int maxDepth1(TreeNode root){
  6.         if(root == null){
  7.             return 0;
  8.         }
  9.         int leftHeight = maxDepth(root.left);//通过递归，求左子树的高度
  10.         int rightHeight = maxDepth(root.right);
  11.         //当通过递归求子树高度的时候，有不平衡的结点的时候，传给两个引用的值为-1，需要在接下
  12. //来的程序中进行判断引用中的值是否大于0，如若不判断引用中的返回值，则会出现上图中3的左子树返
  13. //回为-1，右子树返回为0时，他们差的绝对值为1，这就导致判断出现错误
  14.        if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight-rightHeight) <= 1){
  15.            return Math.max(leftHeight,rightHeight)+1;//平衡返回子树的高度
  16.        }else{
  17.            return -1;//不平衡返回-1.
  18.        }
  19.     }

4.4、时间复杂度的计算

  • 第一个代码：二叉树的结点有N个，每个节点都要判断是否平衡，并且每个子树都要求其高度，求高度的时间复杂度为O(n)，所以第一个判断二叉树是否平衡的方法，其时间复杂度为O(n^{^{2}}).
  • 第二个代码：当求二叉树当中每个子树的高度的同时，也判断了结点是否平衡。当结点不平衡的时候，代码返回-1，判断二叉树平衡的方法isBalanced1，调用求二叉树高度的方法maxDepth1，将其返回值-1传给isBalanced1，isBalanced1判断maxDepth1的返回值是否>=0，小于0，则二叉树不平衡结束。程序结束。所以第二个代码是遇到结点不平衡的时候，程序就会结束，所以它的时间复杂度为O(n).

5、 对称二叉树

5.1、题目要求

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例1：对称的示例

示例2：不对称的示例

5.2、代码思路

判断二叉树对称，它的代码思路与判断两个二叉树是否相同的代码思路相似

  • 首先要判断二叉树的根节点root的左右孩子节点是否对称（leftTree和rightTree）
  • 然后要看两颗树的结构相同，然后再看两棵树的每个结点所对应的值相同。
  • 结构相同的判断都有三种情况：1、两个树都不为空；2、两个树都为空；3、一棵树为空，一棵树不为空。
  • 然后判断leftTree的右孩子节点和rightTree的左孩子节点的值是否相同，判断leftTree的左孩子节点和rightTree的右孩子节点的值是否相同。

5.3、代码示例

  1.     public boolean isSymmetric(TreeNode root){
  2.         if(root == null){//在这个方法中要判断二叉树的根节点是否为空，否则在调用isSymmetricChild方法是可能出现空指针异常。
  3.             return true;
  4.         }
  5.         //这里本质判断的是根的左右孩子结点对不对称
  6.         return isSymmetricChild(root.left,root.right);//将isSymmetricChild方法的返回值，返回给方法的调用者即可。在isSymmetricChild方法中已经判断完root的子树是否对称
  7.     }
  8.  
  9.     public boolean isSymmetricChild(TreeNode p,TreeNode q){
  10.         //判断二叉树的结构是否相同
  11.         if(p == null && q == null){
  12.             return true;
  13.         }
  14.         if(p == null && q != null || p != null && q == null){
  15.             return false;
  16.         }
  17.         //判断二叉树结点的值，是否相同
  18.         if(p.val != q.val){
  19.             return false;
  20.         }
  21.         
  22.         //判断p的左孩子结点是否q的右孩子节点值是否相同；判断p的右孩子结点是否q的左孩子节点值是否相同
  23.         return isSymmetricChild(p.left,q.right)&& isSameTree(p.left,q.right);
  24.     }

6、二叉树的分层遍历（考的比较多）

6.1、通过队列的思想

6.1.1、代码思路（循环思路）

6.1.2、代码示例

  1.     public void levelOrder(TreeNode root){
  2.         if(root == null){
  3.             return ;
  4.         }
  5.         Queue<TreeNode> queue = new LinkedList<>();//队列
  6.         queue.offer(root);
  7.         while(!queue.isEmpty()){//判断队列是否为空
  8.             TreeNode cur = queue.poll();//用cur记录出队列的结点
  9.             System.out.println(cur.val+" ");
  10.             if(cur.left != null){//出队列的结点，是否有左子树
  11.                 queue.offer(cur.left);//存在，将孩子结点放入队列中
  12.             }
  13.             if(cur.right != null){
  14.                 queue.offer(cur.right);
  15.             }
  16.         }
  17.     }

6.2、通过顺序表的嵌套（二维数组）和队列来实现

6.2.1、代码要求

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

6.2.2、代码思路 

将出队列的元素放入到每次循环开辟的顺序表中。然后将顺序表都放入到二维数组中。

 6.2.3、代码示例

  1.     public List<List<Integer>> levelOrder1(TreeNode root) {
  2.         List<List<Integer>> list = new LinkedList<>();//定义一个二维数组
  3.         if(root == null){
  4.             return null;
  5.         }
  6.         Queue<TreeNode> queue = new LinkedList<>();//创建一个队列
  7.         queue.offer(root);//先将根节点放入队列
  8.         while(!queue.isEmpty()){//再判断队列是否为空
  9.             int size = queue.size();//求队列当中的数据个数
  10.             List<Integer> tmp = new ArrayList<>();//这里创建一个顺序表tmp，通过每次循环创建新的顺序表，作为二维数组的元素
  11.             while(size != 0){//通过判断队列当中元素的个数，来判断循环几次，这个while循环每次结束之后，将tmp作为元素，放入到二维数组list当中
  12.                 TreeNode cur = queue.poll();
  13.                 tmp.add(cur.val);//这里将出队列的元素，放入每次循环创建的顺序表中，用来做顺序表的元素
  14.                 size --;
  15.                 if(cur.left != null){//将出队列元素的左孩子节点放入队列中
  16.                     queue.offer(cur.left);
  17.                 }
  18.                 if(cur.right != null) {
  19.                     queue.offer(cur.right);
  20.                 }
  21.             }
  22.             list.add(tmp);//将每个tmp顺序表作为元素放入到二维数组list当中
  23.         }
  24.         return list;//将二叉树遍历完成，最终返回二维数据即可得到层序遍历的结果
  25.     }

7、创建一个二叉树

题目描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述

 输入包括1行字符串，长度不超过100

输出描述

 可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

上述中的二叉树为

代码示例

  1. class TreeNode{
  2.     public char val;
  3.     public TreeNode left;
  4.     public TreeNode right;
  5.     public TreeNode(char val){
  6.         this.val = val;
  7.     }
  8. }
  9. public class Main {
  10.     public static int i = 0;//i属于Main类的，多次调用这个方法的时候，i并不会再每次调用的时候置零
  11.     public static void main(String[] args) {
  12.         Scanner in = new Scanner(System.in);
  13.         //通过这个while循环，将给定的先序遍历字符串读入str中
  14.         while (in.hasNextLine()) { //hasNextLine可以将#号也读入str中
  15.            i = 0;//由于每次使用这个方法的时候，都需要将i置零，所以再这里写i = 0 每次调用这个方法的时候，首先将上次使用这个方法时i的值置为0
  16.            String str = in.nextLine();
  17.            TreeNode root = createTree(str);//调用createTree方法，将遍历到的字符传给createTree,通过先序遍历的方式创建二叉树
  18.            inorder(root);//调用inorder方法，输出中序遍历的结果
  19.         }
  20.     }
  21. //创建二叉树
  22.     public static TreeNode createTree(String str){
  23.        TreeNode root = null;//创建一个空的TreeNode类型的引用指向空的对象
  24.        if(str.charAt(i) != '#'){
  25.            root = new TreeNode(str.charAt(i));//创建一个TreeNode类型的对象结点，内容为得到的i下标的内容
  26.            i++;
  27.            root.left = createTree(str);
  28.            root.right = createTree(str);   
  29.        }else{
  30.             i++;
  31.        }
  32.        return root;//返回root,这里也包括了root为null的情况
  33.     }
  34. //中序遍历
  35.     public static void inorder(TreeNode root){
  36.         if(root == null){
  37.             return ;
  38.         }
  39.         inorder(root.left);
  40.         System.out.print(root.val+" ");
  41.         inorder(root.right);
  42.     }
  43. }

画图理解创建二叉树的代码

❓❓❓这个代码有很多同学会有一点疑问存在，通过i遍历，那么i会不会存在越界的问题。

❗❗❗这里来说不会，先序遍历的字符串。因为得到#号时，就会将递归中的递走完，开始归，当然递了多少次，就归多少次。不会出现越界的问题。

 8、二叉树的最近公共祖先

题目要求

  • 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
  • 公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例

8.1、第一种方法 （递归做法）

 代码示例:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  12.         //先判断是否为空树
  13.         if(root == null){
  14.             return null;
  15.         }
  16.         //判断p和q是不是根节点，若有一个是，那他们的公共祖先就是root。
  17.         if(root == p || root == q){
  18.             return root;
  19.         }
  20.         //若p和q不是root，则通过递归遍历
  21.         TreeNode reftRet = lowestCommonAncestor(root.left,p,q);
  22.         TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
  23.         //根结点左右都不为空，p和q可以再root的左右子树上找到，则root为他们的公共祖先结点
  24.         if(leftRet != null && rightRet != null){
  25.             return root;
  26.         //若是root的右子树上找不到p或者q，左树上可以找到，那么p和q的公共祖先为leftRet
  27.         }else if(leftRet != null){
  28.             return leftRet;
  29.         }else if(rightRet != null){
  30.             return rightRet;
  31.         }
  32.         return null;//上述走完，都没有找到，那么这颗树上没有要找的数字，返回null
  33.     }
  34. }

 

 8.2、第二种方法：利用栈来做

代码示例

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11. //从root开始在二叉树中查找node结点，将路线上的结点放入掉stack中
  12.   public boolean getPath(TreeNode root,TreeNode node,Deque<TreeNode> stack){
  13.       if(root == null || node == null){//如果为空树，或者要查找的node结点不存在
  14.           return false;//返回false
  15.       }
  16.       stack.push(root);//将根节点放入stack中。每放入一个结点，都要进行判断
  17.       if(root == node){//如果根节点是要查找的结点，返回true
  18.           return true;
  19.       }
  20.       boolean ret1 = getPath(root.left,node,stack);//递归root的左子树，查找node结点，将线路上的结点放入到stack中
  21.       if(ret1){//因为ret1中存放的是递归到的结点，接收到的返回值是false或者true，直接进行判断，找到了，返回true,递归结束。若没找到，则向下运行。
  22.           return true;
  23.       }
  24.       boolean ret2 = getPath(root.right,node,stack);
  25.       if(ret2){
  26.           return true;
  27.       }
  28.       //走到这里表示没有找到node，则返回，并在返回的途中将压入的无关结点弹出
  29.       stack.pop();
  30.       return false;//将二叉树遍历完成，还没找到，则返回false
  31.   }
  32.   public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
  33.       //1.两个栈当中 存储数据
  34.       //创建两个栈空间，用来存放找到node结点线路上的所有结点
  35.       Deque<TreeNode> stack1 = new LinkedList<>();
  36.       getPath(root,p,stack1);//调用getPath方法，在二叉树中查找p元素的结点
  37.       Deque<TreeNode> stack2 = new LinkedList<>();
  38.       getPath(root,stack2); 
  39.       //2.判断栈的大小
  40.       int size1 = stack1.size();//计算两个栈中元素的个数
  41.       int size2 = stack2.size();
  42.       if(size1 > size2){//判断如果栈1中的元素个数比栈2中的元素个数多
  43.           int size = size1-size2;//记录多出来的个数
  44.           while(size != 0){
  45.               stack1.pop();//将多出来的元素先弹出来
  46.               size--;
  47.           }
  48.       }else{
  49.           int size = size2-size1;
  50.           while(size != 0){
  51.               stack2.pop();
  52.               size--;
  53.           }
  54.       }
  55.       //栈里面数据的个数是一样的
  56.       while(!stack1.isEmpty()&&!stack2.isEmpty()){
  57.           if(stack1.peek()!=stack2.peek()){//查看两个栈当中的栈顶元素是否相同
  58.               stack1.pop();//若栈顶元素不相同，将栈1和2中的栈顶元素弹出
  59.               stack2.pop();
  60.           }else{
  61.               return stack1.peek();//如果相同则查看栈1中的栈顶元素
  62.           }
  63.       }
  64.       return null;//最终两个栈为空，还没有找到相同的元素，那么就没有找到公共的祖先节点
  65.   }
  66. }

代码思路 

9、 从前序与中序遍历序列构造二叉树

题目要求：

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

题目解析

  • 根据线序遍历找到根节点，然后找根节点对应的在中序遍历中的 位置。
  • 由于先序遍历的顺序为根——》左——》右，所以先创建左孩子结点，再创建有孩子结点。

题目解析

代码示例 

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public int i = 0;
  18.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  19.         return buildTreeChild(preorder,inorder,0,inorder.length-1);//创建二叉树的，从先序遍历的0下标开始建立根节点
  20.     }
  21. //将先序遍历的字符放入数组中，将中序遍历的字符放入到数组中，并给中序遍历的数组中定义开始inbegin和结束inend
  22.     public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend ){
  23.         if(inbegin > inend){//如果inbegin(下标)>inend(下标)，则返回null.表示某个结点没有孩子结点了。
  24.             return null;
  25.         }
  26.         //根据先序遍历创建根节点
  27.         TreeNode root = new TreeNode(preorder[i]);//创建一个新的结点，将先序遍历中的字符放入到创建的节点中，作为每个子树的根节点。
  28.         //找到当前根节点在中序遍历中的位置
  29.         int rootIndex = findIndex(inorder,inbegin,inend,preorder[i]);//在中序遍历的数组中找根节点的位置
  30.         i++;//i下标在先序遍历的数组中，向后挪动一位。
  31.         root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);//创建根节点的左孩子结点。
  32.         root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
  33.         return root;//创建完成之后，返回树的根节点。
  34.     }
  35. //查找目标数字在中序遍历数组中的位置
  36.     private int findIndex(int[] inorder,int inbegin,int inend ,int key){
  37.         for(int i = inbegin;i<=inend;i++){//在中序遍历的数组中inbegin为遍历的起始，inend作为循环的结束
  38.             if(inorder[i] == key){//如果找到，返回i(元素的下标)，没找到返回-1
  39.                 return i;
  40.             }           
  41.         }
  42.         return -1;
  43.     }
  44.     
  45. }

递归演示

10、从中序与后序遍历序列构造二叉树

题目描述

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 

题目解析

根据后续遍历的字符，和中序遍历的字符创建二叉树，根据后序遍历找到根节点，然后根据后序遍历的元素从后往前，先创建右孩子节点，再创建左孩子结点。

代码示例

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public int i = 0;
  18.     public TreeNode buildTree( int[] inorder,int[] postorder ) {
  19.         i = postorder.length-1;//从后往前遍历后续遍历的数组，
  20.         return buildTreeChild(postorder,inorder,0,inorder.length-1);
  21.     }
  22.     public TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend ){
  23.         if(inbegin > inend){
  24.             return null;
  25.         }
  26.         //根据先序遍历创建根节点
  27.         TreeNode root = new TreeNode(postorder[i]);//拿到后序遍历数组的最后一位元素，创建结点
  28.         //找到当前根节点在中序遍历中的位置
  29.         int rootIndex = findIndex(inorder,inbegin,inend,postorder[i]);
  30.         i--;
  31.         root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
  32.         root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
  33.        
  34.         return root;
  35.     }
  36.     private int findIndex(int[] inorder,int inbegin,int inend ,int key){
  37.         for(int i = inbegin;i<=inend;i++){
  38.             if(inorder[i] == key){
  39.                 return i;
  40.             }
  41.         }
  42.         return -1;
  43.     }
  44.  
  45. }

11、根据二叉树创建字符串

题目要求

给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。 

 代码示例

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16.  
  17. class Solution {
  18.     public String tree2str(TreeNode root) {
  19.         if(root == null){
  20.             return null;
  21.         }
  22.         StringBuilder stringBuilder = new StringBuilder();//因为要将最终的结果放入到字符串中，所以创建一个StringBulider类型的对象，用来存放遍历到的结果，为什么用StringBulider而不用String是应为，得到的字符，要经行拼接，String类型的对象不能进行拼接。
  23.         tree2strChilde(root,stringBuilder);
  24.         return stringBuilder.toString();//StringBuilder类型的对象转换成String类型的对象，使用toString方法
  25.     }
  26.     public void tree2strChilde(TreeNode t,StringBuilder stringBuilder){//为什么给tree2strChilde方法一个stringBulider形参，原因是每次递归这个方法的时候，将结果都要放入stringBulider字符串中。
  27.         if(t == null){
  28.             return;
  29.         }
  30.         stringBuilder.append(t.val);//将根的值放入
  31.         if(t.left != null){
  32.             stringBuilder.append("(");
  33.             tree2strChilde(t.left,stringBuilder);
  34.             stringBuilder.append(")");
  35.         }else{
  36.             //左边为空，右边不为空
  37.             if(t.right != null){
  38.                 stringBuilder.append("()");
  39.             }else{//左边为空，右边为空
  40.                 return;
  41.             }
  42.         }
  43.         if(t.right == null){//右边为空
  44.             return ;
  45.         }else{//右边不为空
  46.             stringBuilder.append("(");
  47.             tree2strChilde(t.right,stringBuilder);
  48.             stringBuilder.append(")");
  49.         }
  50.     }
  51. }

代码理解 

12、判断一个树是否为完全二叉树

代码思路

使用队列的思想来完成这个方法。 

在第一次循环中。cur有两种结束方式

第一种：在弹出元素的时候不为空，把左子树和右子树带进来，将整颗树遍历完。最终遇到弹出的元素为null，结束循环。判断队列当中的元素。

第二种：就是在遍历的时候，弹出的某个元素为空，循环结束，判断队列当中剩余的元素。

 代码示例

  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3.  
  4. public class TreeNode {
  5.       int val;
  6.       TreeNode left;
  7.       TreeNode right;
  8.       TreeNode() {}
  9.       TreeNode(int val) { this.val = val; }
  10.       TreeNode(int val, TreeNode left, TreeNode right) {
  11.           this.val = val;
  12.           this.left = left;
  13.           this.right = right;
  14.       }
  15.  
  16.     public boolean isCompleteTree(TreeNode root){
  17.         if (root == null) {
  18.             return true;//这里认为空树也为完全二叉树
  19.         }
  20.         Queue<TreeNode> queue = new LinkedList<>();//定义一个对列，用来存放结点
  21.         queue.offer(root);//如果不是空树，将根节点放入队列当中
  22.         while(!queue.isEmpty()){//当队列不为空时，进入循环
  23.             TreeNode cur = queue.poll();//定义一个cur，用来记录弹出队列的元素
  24.             if(cur != null){//如果弹出队列的元素不为空
  25.                 queue.offer(cur.left);//则将弹出队列的左右孩子结点，放入队列当中
  26.                 queue.offer(cur.right);
  27.             }else{//如果弹出队列的元素为空
  28.                 break;//则直接结束
  29.             }
  30.         }
  31.         //判断队列当中的剩余元素，
  32.         while (!queue.isEmpty()) {
  33.             TreeNode tmp = queue.poll();//用tmp记录弹出队列的元素
  34.             if (tmp != null) {//如果弹出队列的元素不为空，则返回false，则这个二叉树不是完全二叉树
  35.                 return false;
  36.             }
  37.         }
  38.         return true;//将队列中的元素遍历完，也没有遇到非空元素，则这个二叉树为完全二叉树
  39.     }
  40. }

 

12、二叉树前序遍历非递归实现 

代码思路

 代码示例

  1. import java.util.ArrayDeque;
  2. import java.util.Deque;
  3. public class TreeNode {
  4.       int val;
  5.       TreeNode left;
  6.       TreeNode right;
  7.       TreeNode() {}
  8.       TreeNode(int val) { this.val = val; }
  9.       TreeNode(int val, TreeNode left, TreeNode right) {
  10.           this.val = val;
  11.           this.left = left;
  12.           this.right = right;
  13.       }
  14.  
  15.     public void preOrderNor(TreeNode root){
  16.         if (root == null) {
  17.             return ;
  18.         }
  19.         TreeNode cur = root;//定义一个跑腿引用，用来代替root遍历二叉树
  20.         Deque<TreeNode> stack = new ArrayDeque<>();//定义栈，存放每个子树根节点
  21.         while(cur != null || stack.isEmpty()) {
  22.             while (cur != null) {//如果根节点不为空，则进入循环
  23.                 stack.push(cur);//将cur指向的根节点放入栈中
  24.                 System.out.println(cur.val + " ");//并且将其数值打印
  25.                 cur = cur.left;//然后在遍历根节点的左子树
  26.             }
  27.             TreeNode top = stack.pop();//如果根节点为空，弹出栈顶元素，用top记录
  28.             cur = top.right;//cur指向弹出元素的右子树
  29.         }
  30.     }
  31. }

13、二叉树中序遍历非递归实现

代码思路

代码示例

  1.  
  2. import java.util.ArrayDeque;
  3. import java.util.Deque;
  4. public class TreeNode {
  5.       int val;
  6.       TreeNode left;
  7.       TreeNode right;
  8.       TreeNode() {}
  9.       TreeNode(int val) { this.val = val; }
  10.       TreeNode(int val, TreeNode left, TreeNode right) {
  11.           this.val = val;
  12.           this.left = left;
  13.           this.right = right;
  14.       }
  15.     public void inOrderNor(TreeNode root){
  16.         if (root == null) {
  17.             return ;
  18.         }
  19.         TreeNode cur = root;//定义一个跑腿引用，用来代替root遍历二叉树
  20.         Deque<TreeNode> stack = new ArrayDeque<>();//定义栈，存放每个子树根节点
  21.         while(cur != null || stack.isEmpty()) {
  22.             while (cur != null) {//如果根节点不为空，则进入循环
  23.                 stack.push(cur);//将cur指向的根节点放入栈中
  24.                 cur = cur.left;//然后在遍历根节点的左子树
  25.             }
  26.             TreeNode top = stack.pop();//如果根节点为空，弹出栈顶元素，用top记录
  27.             System.out.println(top.val + " ");//并且将其数值打印
  28.             cur = top.right;//cur指向弹出元素的右子树
  29.         }
  30.     }
  31. }

 14、二叉树中后续遍历非递归实现

 代码思路

代码示例

  1. import java.util.ArrayDeque;
  2. import java.util.Deque;
  3. public class TreeNode {
  4.       int val;
  5.       TreeNode left;
  6.       TreeNode right;
  7.       TreeNode() {}
  8.       TreeNode(int val) { this.val = val; }
  9.       TreeNode(int val, TreeNode left, TreeNode right) {
  10.           this.val = val;
  11.           this.left = left;
  12.           this.right = right;
  13.       }
  14.     public void postOrderNor(TreeNode root){
  15.         if (root == null) {
  16.             return ;
  17.         }
  18.         TreeNode cur = root;
  19.         TreeNode prev = null;
  20.         Deque<TreeNode> stack = new ArrayDeque<>();
  21.         while(cur != null || !stack.isEmpty()){
  22.             while(cur != null){
  23.                 stack.push(cur);
  24.                 cur = cur.left;
  25.             }
  26.             TreeNode top = stack.peek();//这里不能弹出，当左右子树都遍历完成之后，才能弹出元素，所以这里使用查看。
  27.             if (top.right == null || top.right == prev) {//如果被查看的元素右子树为空，或者是被查看的元素的右子树已经被打印过，则进入该循环，打印，弹出，记录被查看的元素
  28.                 System.out.println(top.val+" ");
  29.                 stack.pop();
  30.                 prev = top;//这里使用prev将打印的元素记录下来
  31.             }else{//如果被查看的元素的右子树不为空，则cur遍历到被查看的元素的右子树。
  32.                 cur = top.right;
  33.             }
  34.         }
  35.         System.out.println();
  36.     }
  37. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/290215
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号