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

二叉树练习题（数据结构系列10）_数据结构二叉树题库

作者：码创造者 | 2024-07-25 07:46:59

赞

踩

数据结构二叉树题库

目录

前言：

习题：

1. 检查两颗树是否相同。

2. 另一颗树的子树。

3. 翻转二叉树。

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

5. 对称二叉树。

6. 二叉树的构建及遍历。

7. 二叉树的分层遍历 。

8. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。

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

10. 根据一棵树的中序遍历与后序遍历构造二叉树。

11. 二叉树创建字符串。

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

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

14. 二叉树后序非递归遍历实现。

结束语：

前言：

上一次的博客中小编主要与大家分享了树、二叉树、满二叉树与完全二叉树的一些基础知识点，以及我们简单的实现了一些二叉树当中的一些算法，那么接下来我们就利用我们上次所学习的知识来进一步的展开练习一下吧！

习题：

1. 检查两颗树是否相同。

题目描述：

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

如下所示的两颗数数就是相同的树。

而下面的两颗树就不是相同的树，虽然结构一样但是值不一样也不是相同的树。

思路：
1.先判断两个树的根节点是不为空的，如果两者的树的根节点都是空的，那么也就说明二者的结构和值都是一样的。

2.在判断二者的结构是不是一样的如果一个是空的一个是不为空的那么说明这两颗树不是相同的树，否则就是一样的。

3.如果结构相同的话就判断它两的值是不是一样的，如果是一样的话就继续递归调用该函数向两颗树的左右分别向下查看，否则就直接返回false。

两颗树代码如下所示：
 

  1. public class BinaryTree {
  2.     public static class TreeNode{
  3.         public int val;//值
  4.         public TreeNode left;//左孩子
  5.         public TreeNode right;//右孩子
  6.  
  7.         public TreeNode(int val) {
  8.             this.val = val;
  9.         }
  10.     }
  11.  
  12.     TreeNode root = null;//根节点
  13.  
  14.     public TreeNode createTreeP() {
  15.         TreeNode node1 = new TreeNode(1);
  16.         TreeNode node2 = new TreeNode(2);
  17.         TreeNode node3 = new TreeNode(3);
  18.         TreeNode node4 = new TreeNode(4);
  19.         TreeNode node5 = new TreeNode(5);
  20.         TreeNode node6 = new TreeNode(6);
  21.         TreeNode node7 = new TreeNode(7);
  22.         //进行关联
  23.         root = node1;
  24.         node1.left = node2;
  25.         node1.right = node3;
  26.         node2.left = node4;
  27.         node2.right = node5;
  28.         node3.left = node6;
  29.         node3.right = node7;
  30.         return node1;
  31.     }
  32.  
  33.  
  34.     public TreeNode createTreeQ() {
  35.         TreeNode node1 = new TreeNode(1);
  36.         TreeNode node2 = new TreeNode(2);
  37.         TreeNode node3 = new TreeNode(3);
  38.         TreeNode node4 = new TreeNode(4);
  39.         TreeNode node5 = new TreeNode(5);
  40.         TreeNode node6 = new TreeNode(6);
  41.         TreeNode node7 = new TreeNode(7);
  42.         //进行关联
  43.         root = node1;
  44.         node1.left = node2;
  45.         node1.right = node3;
  46.         node2.left = node4;
  47.         node2.right = node5;
  48.         node3.left = node6;
  49.         node3.right = node7;
  50.         return node1;
  51.     }
  52. }

核心代码实现如下所示：
 

  1. public boolean isSameTree(TreeNode p, TreeNode q) {
  2.         //两个都是空
  3.         if (p == null && q == null) {
  4.             return true;
  5.         }
  6.         //一个是空一个不为空
  7.         if (p != null && q == null || p == null && q != null)  {
  8.             return false;
  9.         }
  10.         if (p.val != q.val) {
  11.             return false;
  12.         }
  13.         //来到这里说明两者的值是一样的，且两者的结构是一样的。
  14.         return isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);
  15.     }

结果如下所示：


2. 另一颗树的子树。

问题描述：

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

如下所示的两颗树，一颗树是另一颗树的子树。

创建的两颗树的代码：
 

  1. public static class TreeNode{
  2.         public int val;//值
  3.         public TreeNode left;//左孩子
  4.         public TreeNode right;//右孩子
  5.  
  6.         public TreeNode(int val) {
  7.             this.val = val;
  8.         }
  9.     }
  10.  
  11.     TreeNode root = null;//根节点
  12.  
  13.     public TreeNode createTreeP() {
  14.         TreeNode node1 = new TreeNode(1);
  15.         TreeNode node2 = new TreeNode(2);
  16.         TreeNode node3 = new TreeNode(3);
  17.         TreeNode node4 = new TreeNode(4);
  18.         TreeNode node5 = new TreeNode(5);
  19.         TreeNode node6 = new TreeNode(6);
  20.         TreeNode node7 = new TreeNode(7);
  21.         //进行关联
  22.         root = node1;
  23.         node1.left = node2;
  24.         node1.right = node3;
  25.         node2.left = node4;
  26.         node2.right = node5;
  27.         node3.left = node6;
  28.         node3.right = node7;
  29.         return node1;
  30.     }
  31.  
  32.  
  33.     public TreeNode createTreeQ() {
  34.         TreeNode node1 = new TreeNode(2);
  35.         TreeNode node2 = new TreeNode(4);
  36.         TreeNode node3 = new TreeNode(5);
  37.         //进行关联
  38.         root = node1;
  39.         node1.left = node2;
  40.         node1.right = node3;
  41.         return node1;
  42.     }

核心代码如下所示：

  1. public boolean isSubtree(TreeNode root, TreeNode subRoot) {
  2.         //1.判断根是不是相同
  3.         if (root == null && subRoot == null) {
  4.             return true;
  5.         }
  6.         //判断两颗是不是一样
  7.         if (isSameTree(root,subRoot)) {
  8.             return true;
  9.         }
  10.         //判断root的左子树是不是和subRoot一样
  11.         if (isSameTree(root.left, subRoot)) {
  12.             return true;
  13.         }
  14.         //判断root的右子树和subRoot是不是一样
  15.         if (isSameTree(root.right,subRoot)) {
  16.             return true;
  17.         }
  18.         return false;
  19.     }
  20.     public boolean isSameTree(TreeNode p, TreeNode q) {
  21.         //两个都是空
  22.         if (p == null && q == null) {
  23.             return true;
  24.         }
  25.         //一个是空一个不为空
  26.         if (p != null && q == null || p == null && q != null)  {
  27.             return false;
  28.         }
  29.         if (p.val != q.val) {
  30.             return false;
  31.         }
  32.         //来到这里说明两者的值是一样的，且两者的结构是一样的。
  33.         return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
  34.     }


结果如下所示：


3. 翻转二叉树。

问题描述：

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

如下所示：

树的代码如下所示：
 

  1. public static class TreeNode {
  2.         public int val;
  3.         public TreeNode left;
  4.         public TreeNode right;
  5.  
  6.         public TreeNode(int val) {
  7.             this.val = val;
  8.         }
  9.     }
  10.  
  11.     TreeNode root = null;
  12.  
  13.     public TreeNode createTree() {
  14.         TreeNode node1 = new TreeNode(1);
  15.         TreeNode node2 = new TreeNode(2);
  16.         TreeNode node3 = new TreeNode(3);
  17.         TreeNode node4 = new TreeNode(4);
  18.         TreeNode node5 = new TreeNode(5);
  19.  
  20.         //关联
  21.         root = node1;
  22.         node1.left = node2;
  23.         node1.right = node3;
  24.         node2.left = node4;
  25.         node2.right = node5;
  26.         return root;
  27.     }

核心代码如下所示：

  1. public TreeNode invertTree(TreeNode root) {
  2.         TreeNode cur = root;
  3.         if (root == null) {
  4.             return null;
  5.         }
  6.         //交换
  7.         TreeNode tmp = root.left;
  8.         root.left = root.right;
  9.         root.right = tmp;
  10.         //继续交换左右子树的孩子结点
  11.         invertTree(root.left);
  12.         invertTree(root.right);
  13.         return cur;
  14.     }


结果如下所示：


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

问题描述：

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

如上图所示，对于结点1来说左树的高度是4，右树的高度是2，左右高度差是2，超过了1，所以不是一颗高度平衡的二叉树。

但是下面的这个就是一颗高度平衡的二叉树。

创建树的代码如下所示：
 

  1.     public static class TreeNode{
  2.         public int val;
  3.         public TreeNode left;
  4.         public TreeNode right;
  5.  
  6.         public TreeNode(int val) {
  7.             this.val = val;
  8.         }
  9.     }
  10.  
  11.     TreeNode root = null;
  12.  
  13.     public TreeNode createTree() {
  14.         TreeNode node1 = new TreeNode(1);
  15.         TreeNode node2 = new TreeNode(2);
  16.         TreeNode node3 = new TreeNode(3);
  17.         TreeNode node4 = new TreeNode(4);
  18.         TreeNode node5 = new TreeNode(5);
  19.         TreeNode node6 = new TreeNode(6);
  20.         TreeNode node7 = new TreeNode(7);
  21.         TreeNode node8 = new TreeNode(8);
  22.  
  23.         //关联
  24.         root = node1;
  25.         node1.left = node2;
  26.         node1.right = node3;
  27.         node2.left = node4;
  28.         node2.right = node5;
  29.         node3.left = node6;
  30.         node4.left = node7;
  31.         node4.right = node8;
  32.         return root;
  33.     }

核心代码如下所示：

  1.     //判断是不是高度平衡的二叉树
  2.     public boolean isBalanced(TreeNode root){
  3.         return treeHeight(root) >= 0;
  4.     }
  5.  
  6.     //计算二叉树的高度
  7.     public int treeHeight(TreeNode root) {
  8.         if (root == null) {
  9.             return 0;
  10.         }
  11.         int leftHeight = treeHeight(root.left);
  12.         if (leftHeight < 0) {
  13.             return -1;
  14.         }
  15.         int rightHeight = treeHeight(root.right);
  16.         if (rightHeight < 0) {
  17.             return -1;
  18.         }
  19.         if (Math.abs(leftHeight - rightHeight) <= 1) {
  20.             return Math.max(leftHeight,rightHeight) + 1;
  21.         } else {
  22.             return -1;
  23.         }
  24.     }


结果如下所示：


5. 对称二叉树。

问题描述：

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

如下所示就是一颗对称的二叉树。

上述树的代码如下所示：

  1.     public static class TreeNode{
  2.         public int val;
  3.         public TreeNode left;
  4.         public TreeNode right;
  5.  
  6.         public TreeNode(int val) {
  7.             this.val = val;
  8.         }
  9.     }
  10.  
  11.     TreeNode root = null;
  12.  
  13.     public TreeNode createTree() {
  14.         TreeNode node1 = new TreeNode(1);
  15.         TreeNode node2 = new TreeNode(2);
  16.         TreeNode node3 = new TreeNode(2);
  17.         TreeNode node4 = new TreeNode(3);
  18.         TreeNode node5 = new TreeNode(3);
  19.         TreeNode node6 = new TreeNode(4);
  20.         TreeNode node7 = new TreeNode(4);
  21.  
  22.         //关联
  23.         root = node1;
  24.         node1.left = node2;
  25.         node1.right = node3;
  26.         node2.left = node4;
  27.         node2.right = node6;
  28.         node3.left = node7;
  29.         node3.right = node5;
  30.         return root;
  31.     }

构造的树的结果如下所示：

核心代码如下所示：

  1. //判断该树是否是对称二叉树
  2.     public boolean isSymmetric(TreeNode root){
  3.         if (root == null) {
  4.             return true;
  5.         }
  6.         //判断子树的两边是不是对称的
  7.         return isSymmetricChild(root.left,root.right);
  8.     }
  9.  
  10.     public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
  11.         if (leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
  12.             return false;
  13.         }
  14.         if (leftTree == null && rightTree == null) {
  15.             return true;
  16.         }
  17.         if (leftTree.val != rightTree.val) {
  18.             return false;
  19.         }
  20.         return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);
  21.     }


结果如下所示：

6. 二叉树的构建及遍历。

问题描述：

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

上述的前序遍历构建出来的二叉树如下所示：

思路：
这道题我们主要考虑的就是如何用前序遍历的方式创建出一颗二叉树，首先我们拿到的是一串字符串，其次我们就开始遍历字符串的每一个值，当我们遇到‘#’的时候就说明这课树的左孩子是没有的，如果接着在次遇到‘#’就说明这个结点的右孩子也是没有的。如果我们遍历到的是一个字母，我们就直接新建一个结点，然后再去以递归的方式去创建左孩子结点和右孩子结点就可以了。

创建出来的二叉树：
 

  1. public class BinaryTree {
  2.     static class TreeNode{
  3.         public char val;
  4.         public TreeNode left;
  5.         public TreeNode right;
  6.  
  7.         public TreeNode(char val) {
  8.             this.val = val;
  9.         }
  10.     }
  11.  
  12.     TreeNode root = null;
  13. }

核心代码如下所示：

  1. public class Test1 {
  2.     //以前序遍历的方式创建一颗二叉树
  3.     public static int i;
  4.     public static BinaryTree.TreeNode crateTree(String str) {
  5.         BinaryTree.TreeNode root = null;
  6.         if (str.charAt(i) != '#') {
  7.             root = new BinaryTree.TreeNode(str.charAt(i));
  8.             i++;
  9.             root.left = crateTree(str);
  10.             root.right = crateTree(str);
  11.         }else {
  12.             i++;
  13.         }
  14.         return root;
  15.     }
  16.     //先序遍历
  17.     public static void inOrder(BinaryTree.TreeNode root) {
  18.         if (root == null) {
  19.             return;
  20.         }
  21.         inOrder(root.left);
  22.         System.out.print(root.val +" ");
  23.         inOrder(root.right);
  24.     }
  25.     public static void main(String[] args) {
  26.         String str = "ABC##DE#G##F###";
  27.         BinaryTree.TreeNode ret = crateTree(str);
  28.         inOrder(ret);
  29.     }
  30. }


结果如下所示：


7. 二叉树的分层遍历 。

问题描述：

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

如下图所示二叉树的层序遍历就是：3-9-20-15-7

思路：
我们可以借助队列来完成它，先将树的根节点入队，如果队列中的元素不为空，那么我们就直接出队首元素，打印并且如果将他的左右孩子结点依次入队。如果没有孩子结点的话就继续出队，直到队列为空为止。

树的创建：
 

  1. class TreeNode3 {
  2.     int val;
  3.     TreeNode3 left;
  4.     TreeNode3 right;
  5.     TreeNode3() {
  6.  
  7.     }
  8.     TreeNode3(int val) {
  9.         this.val = val;
  10.     }
  11.     TreeNode3(int val, TreeNode3 left, TreeNode3 right) {
  12.         this.val = val;
  13.         this.left = left;
  14.         this.right = right;
  15.     }
  16.  
  17.     public TreeNode3 root;
  18.     public TreeNode3 createTree() {
  19.         TreeNode3 node1 = new TreeNode3(3);
  20.         TreeNode3 node2 = new TreeNode3(9);
  21.         TreeNode3 node3 = new TreeNode3(20);
  22.         TreeNode3 node4 = new TreeNode3(15);
  23.         TreeNode3 node5 = new TreeNode3(7);
  24.  
  25.         node1.left =  node2;
  26.         node1.right = node3;
  27.         node3.left = node4;
  28.         node3.right = node5;
  29.         this.root = node1;
  30.         return root;
  31.     }
  32. }

核心代码如下所示：

  1. public static void levelOrder(TreeNode3 root) {
  2.         if (root == null) {
  3.             return;
  4.         }
  5.         Queue<TreeNode3> queue = new LinkedList<>();
  6.         TreeNode3 cur = root;
  7.         queue.offer(cur);
  8.         while (!queue.isEmpty()) {
  9.             TreeNode3 top = queue.poll();
  10.             //出队首元素
  11.             System.out.print(top.val + " ");
  12.             if (top.left != null) {
  13.                 queue.offer(top.left);
  14.             }
  15.             if (top.right != null) {
  16.                 queue.offer(top.right);
  17.             }
  18.         }
  19.     }


结果如下所示： 


8. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。

问题描述：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

如下图所示其中结点5和结点1的最近公共祖先是结点3。

 思路：

p和q的位置一共存在三种情况如下图所示：
 

该树的代码如下所示：

  1. class TreeNode{
  2.         public int val;
  3.         public TreeNode left;
  4.         public TreeNode right;
  5.  
  6.         public TreeNode(int val) {
  7.             this.val = val;
  8.         }
  9.     }
  10.  
  11.     public TreeNode root;
  12.  
  13.     public TreeNode createTree() {
  14.         TreeNode node1 = new TreeNode(1);
  15.         TreeNode node2 = new TreeNode(2);
  16.         TreeNode node3 = new TreeNode(3);
  17.         TreeNode node4 = new TreeNode(4);
  18.         TreeNode node5 = new TreeNode(5);
  19.         TreeNode node6 = new TreeNode(6);
  20.         TreeNode node7 = new TreeNode(7);
  21.         TreeNode node8 = new TreeNode(8);
  22.         TreeNode node0 = new TreeNode(0);
  23.  
  24.         node3.left = node5;
  25.         node3.right = node1;
  26.         node5.left = node6;
  27.         node5.right = node2;
  28.         node2.left = node7;
  29.         node2.right = node4;
  30.         node1.left = node0;
  31.         node1.right = node8;
  32.         this.root = node3;
  33.  
  34.         return root;
  35.     }

核心代码如下所示：

  1. //最近公共祖先
  2.     public int lowestCommonAncestor(TreeNode root, int p, int q) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  6.         //1.先判断根节点是不是其中的一个
  7.         if (root.val == p || root.val == q) {
  8.             return root.val;
  9.         }
  10.         //2.如果不是其中的一个那么就向左和右分别递归的找p和q
  11.         int leftRet = lowestCommonAncestor(root.left,p,q);
  12.         int rightRet = lowestCommonAncestor(root.right,p,q);
  13.         //如果左右都找到了p和q,也就是我们上图分析的第一种情况p和q在root的两侧.
  14.         if (leftRet != 0 && rightRet != 0) {
  15.             return root.val;
  16.         } else if (leftRet != 0) {
  17.             //如果右边没有找到p或者是q，左边找到了，那么就返回左边。
  18.             return leftRet;
  19.         } else if (rightRet != 0) {
  20.             //如果左边没有找到p或者是q，右边找到了，那么就返回右边。
  21.             return rightRet;
  22.         }
  23.         return 0;
  24.     }


结果如下所示：


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

问题描述：

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

思路详细看代码解释。

核心代码如下所示：

  1. //根据前序遍历的顺序和中序遍历的顺序构建二叉树
  2.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  3.         int len = preorder.length;
  4.         return buildTreeChild(preorder,inorder,0,len - 1);
  5.     }
  6.  
  7.     /**
  8.      *
  9.      * @param preorder
  10.      * @param inorder
  11.      * @param begin:构建树结点的起始位置
  12.      * @param end：构建树结点结束的位置
  13.      * @return
  14.      */
  15.     public int i = 0;
  16.  
  17.     public TreeNode buildTreeChild(int[] preorder, int[] inorder, int begin, int end) {
  18.         //如果起始位置大于终止位置说明没有结点了
  19.         if (begin > end) {
  20.             return null;
  21.         }
  22.         //创建一个新的结点，新的结点就是直接来自前序遍历按顺序下来的结点。
  23.         TreeNode root = new TreeNode(preorder[i]);
  24.         //找到根结点在中序遍历中的位置
  25.         int index = FindIndex(inorder,begin,end,preorder[i]);
  26.         i++;
  27.         //递归创建左树和右树
  28.         root.left = buildTreeChild(preorder, inorder, begin, index - 1);
  29.         root.right = buildTreeChild(preorder, inorder, index + 1, end);
  30.         return root;
  31.     }
  32.     private int FindIndex(int[] inorder, int begin, int end, int key) {
  33.         for (int k = begin; k <= end; k++) {
  34.             if (inorder[k] == key) {
  35.                 return k;
  36.             }
  37.         }
  38.         return -1;
  39.     }


10. 根据一棵树的中序遍历与后序遍历构造二叉树。

问题描述：

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

思想：

结合上述根据一棵树的前序遍历与中序遍历构造二叉树我们就可以大概知道如何构造了，与上一个问题不同的点就是我们需要先构造右孩子结点在构造左孩子结点。，具体的思想看代码注释。

核心代码如下所示：

  1. public TreeNode buildTree(int[] inorder, int[] postorder) {
  2.         i = postorder.length - 1;
  3.         return buildTreeChild(inorder,postorder,0, i);
  4.     }
  5.  
  6.     public int i = 0;
  7.  
  8.     public TreeNode buildTreeChild(int[] inorder, int[] postorder, int begin, int end) {
  9.         if (begin > end) {
  10.             return null;
  11.         }
  12.         //后续遍历中的最后一个值就是根结点
  13.         TreeNode root = new TreeNode(postorder[i]);
  14.         //寻找后续遍历中根结点在中序遍历中的下标值
  15.         int rootIndex = findIndex(inorder, begin, end, postorder[i]);
  16.         i--;
  17.         //向下去一递归构造左右子树
  18.         root.right = buildTreeChild(inorder, postorder, rootIndex + 1, end);
  19.         root.left = buildTreeChild(inorder, postorder, begin,rootIndex - 1);
  20.  
  21.         return root;
  22.     }
  23.  
  24.     //计算根结点在中序遍历中的下标值
  25.     private int findIndex(int[] inorder, int begin, int end, int key) {
  26.         for (int j = begin; j <= end; j++) {
  27.             if (inorder[j] == key) {
  28.                 return j;
  29.             }
  30.         }
  31.         return -1;
  32.     }

 


11. 二叉树创建字符串。

问题描述：

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

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

 

思路：

首先我们先明确一点就是我们是通过二叉树的前序遍历俩创建字符串的，那么我们就来看一下上述这课二叉树的前序遍历是：1-2-4-3，那么我们通过前序遍历后转化成字符串就是1(2(4))(3)，我们发现当我们遍历一颗树的左子树的时候我们会先入一个“（ ”，然后再进行数字的打印如果没有左子树的的话那就直接打印一个“（）”，然后我们在继续进行右子树的遍历。具体的解释详细见代码。

树的创建代码：
 

  1. class TreeNode {
  2.     int val;
  3.     TreeNode left;
  4.     TreeNode right;
  5.     TreeNode() {}
  6.     TreeNode(int val) { this.val = val; }
  7.     TreeNode(int val, TreeNode left, TreeNode right) {
  8.         this.val = val;
  9.         this.left = left;
  10.         this.right = right;
  11.     }
  12.  
  13.     public TreeNode root;
  14.     public TreeNode createTree() {
  15.         TreeNode node1 = new TreeNode(1);
  16.         TreeNode node2 = new TreeNode(2);
  17.         TreeNode node3 = new TreeNode(3);
  18.         TreeNode node4 = new TreeNode(4);
  19.  
  20.         node1.left =  node2;
  21.         node1.right = node3;
  22.         node2.left = node4;
  23.         this.root = node1;
  24.         return root;
  25.     }
  26. }

核心代码如下所示：

  1. public static String tree2str(TreeNode root) {
  2.         if (root == null) {
  3.             return null;
  4.         }
  5.         //创建一个StringBuilder来保存字符串
  6.         StringBuilder stringBuilder = new StringBuilder();
  7.         tree2strChild(root,stringBuilder);
  8.         return stringBuilder.toString();
  9.     }
  10.  
  11.     public static void tree2strChild(TreeNode root, StringBuilder stringBuilder) {
  12.         if (root == null ) {
  13.             return;
  14.         }
  15.         //如果根结点的值不为空，就将根结点的值先放进来
  16.         stringBuilder.append(root.val);
  17.         //判断是否有左子树
  18.         if (root.left != null) {
  19.             //存在左子树就先打印 ( ，然后再进行递归调用他的左子树，结束后打印 )
  20.             stringBuilder.append("(");
  21.             tree2strChild(root.left,stringBuilder);
  22.             stringBuilder.append(")");
  23.         }else {
  24.             //左边为空
  25.             if (root.right != null) {
  26.                 //右边不为空
  27.                 stringBuilder.append("()");
  28.             }else {
  29.                 //左右都是空的
  30.                 return;
  31.             }
  32.         }
  33.         //如果右子树不为空的话和左边不为空的情况一样，先打印 ( ,然后再递归调用它的右子树，最后打印 )。
  34.         if (root.right == null) {
  35.             return;
  36.         }else {
  37.             //右边不为空
  38.             stringBuilder.append("(");
  39.             tree2strChild(root.right,stringBuilder);
  40.             stringBuilder.append(")");
  41.         }
  42.     }


结果如下所示：

 

 

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

问题描述：

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

思路：

我们之前是通过递归来实现一颗二叉树的前序遍历的那么现在我们要用非递归要怎么实现呢？
我们是通过借助栈来实现的，首先我们先定义一个结点变量cur来记录当前的根结点，如果说根结点不等于null或者是栈不为空的时候我们就进入循环中，如果cur不为空，那么我们就让当前的结点入栈并打印，然后我们在让cur = cur.left。也就是继续往左边走，如果左边的子树为空的话我就跳出里面的循环往右边走，我可以在定义一个变量top用来记录当前的栈弹出的元素，然后我们将这弹出元素的右子树的结点赋值给cur，然后再进行循环。

树的代码如下所示：
 

  1. class TreeNode2 {
  2.     int val;
  3.     TreeNode2 left;
  4.     TreeNode2 right;
  5.     TreeNode2() {}
  6.     TreeNode2(int val) { this.val = val; }
  7.     TreeNode2(int val, TreeNode2 left, TreeNode2 right) {
  8.         this.val = val;
  9.         this.left = left;
  10.         this.right = right;
  11.     }
  12.  
  13.     public TreeNode root;
  14.     public TreeNode createTree() {
  15.         TreeNode node1 = new TreeNode(1);
  16.         TreeNode node2 = new TreeNode(2);
  17.         TreeNode node3 = new TreeNode(3);
  18.  
  19.         node1.right = node2;
  20.         node2.left = node3;
  21.  
  22.         this.root = node1;
  23.         return root;
  24.     }
  25. }

核心代码如下所示：

  1. public static void preorderTraversal(TreeNode root) {
  2.         if (root == null) {
  3.             return;
  4.         }
  5.         TreeNode cur = root;
  6.         Deque<TreeNode> stack = new LinkedList<>();
  7.         while (cur != null || !stack.isEmpty())  {
  8.             while (cur != null) {
  9.                 stack.push(cur);
  10.                 System.out.print(cur.val + " ");
  11.                 cur = cur.left;
  12.             }
  13.             TreeNode top = stack.pop();
  14.             cur = top.right;
  15.         }
  16.     }


结果如下所示：

 


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

问题描述：

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

 思想：

同样以上面这课二叉树为例，我们的基本思想和前序遍历的一样也是借助栈来完成的，只是我们打印根结点的时间不一样了。

核心代码如下所示：

  1. public static void inorderTraversal(TreeNode root) {
  2.         if (root == null) {
  3.             return;
  4.         }
  5.         TreeNode cur = root;
  6.         Deque<TreeNode> stack = new LinkedList<>();
  7.         while (cur != null || !stack.isEmpty()) {
  8.             while (cur != null) {
  9.                 stack.push(cur);//将根结点入栈
  10.                 cur = cur.left;//在继续往左边走
  11.             }
  12.             TreeNode top = stack.pop();//弹出栈顶元素
  13.             System.out.print(top.val + " ");
  14.             cur = top.right;
  15.         }
  16.     }


结果如下所示：

 


14. 二叉树后序非递归遍历实现。

问题描述：

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

核心代码如下所示：

  1. public static void postorderTraversal(TreeNode root) {
  2.         if (root == null) {
  3.             return;
  4.         }
  5.         TreeNode cur = root;
  6.         TreeNode prev = null;//用来记录打印过的结点
  7.         Deque<TreeNode> stack = new LinkedList<>();
  8.         while (cur != null || !stack.isEmpty()) {
  9.             while (cur != null) {
  10.                 stack.push(cur);
  11.                 cur = cur.left;
  12.             }
  13.             TreeNode top = stack.peek();
  14.             if (top.right == null || top.right == prev) {
  15.                 System.out.print(top.val + " ");
  16.                 stack.pop();
  17.                 prev = top;
  18.             }else {
  19.                 cur = top.right;
  20.             }
  21.         }
  22.     }


结果如下所示：

 


结束语：

好啦，有关于二叉树的一些基础练习题小编就与大家分享到这里啦！想要继续深度学习的同学也可以自己去刷一些题，来加强对知识的理解，希望对大家有所帮助，想要学习的同学记得关注小编和小编一起学习吧！如果文章中有任何错误也欢迎各位大佬及时为小编指点迷津（在此小编先谢过各位大佬啦！）

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

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

  

闽ICP备14008679号