devbox
程序代码艺术家2
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

初阶数据结构（7）（树形结构的概念和相关重要定义、树的表示形式、树的应用、二叉树【两种特殊的二叉树、性质、存储、遍历、基本操作、二叉树相关的 OJ 题】）

作者：程序代码艺术家2 | 2024-02-01 09:15:12

赞

踩

初阶数据结构（7）（树形结构的概念和相关重要定义、树的表示形式、树的应用、二叉树【两种特殊的二叉树、性质、存储、遍历、基本操作、二叉树相关的 OJ 题】）

接上次博客：初阶数据结构（6）（队列的概念、常用的队列方法、队列模拟实现【用双向链表实现、用数组实现】、双端队列 (Deque)、OJ练习【用队列实现栈、用栈实现队列】）_di-Dora的博客-CSDN博客

目录

树形结构的概念

一些重要概念：

树的表示形式

树的应用

二叉树

 两种特殊的二叉树

二叉树的性质

二叉树的存储

二叉树的遍历

1. 前中后序遍历

2. 层序遍历

二叉树的基本操作

二叉树相关的 OJ 题

1. 检查两颗树是否相同

2. 另一颗树的子树

3. 翻转二叉树

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

5. 对称二叉树

6. 二叉树的构建及遍历

7. 二叉树的分层遍历

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

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

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

11. 二叉树创建字符串

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

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

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

树形结构的概念

 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合，这些结点之间通过边连接。树具有层次关系，它的形状类似于一棵倒挂的树，根节点位于顶部，叶节点位于底部。

树的定义包括以下要点：

  1. 根节点（Root）：树中的一个特殊节点，它没有前驱节点，是整个树的起点。
  2. 子树（Subtree）：除根节点外，树中的每个节点都可以看作是一棵子树的根节点。子树是一棵与原树类似的树，它包含了一部分原树中的节点和边。
  3. 前驱节点（Parent）和后继节点（Children）：一个节点的前驱节点是其所在子树的根节点，而该节点称为前驱节点的后继节点。每个节点可以有零个或多个后继节点。
  4. 叶节点（Leaf）：没有后继节点的节点称为叶节点，也称为终端节点。叶节点位于树的底部，它们没有子树。

注意：

  • 树的结构是递归定义的，每个节点都可以看作是一个根节点，包含了一棵子树。
  • 树形结构中，子树之间不能有交集，即子树是不相交的，否则就不是树形结构
  • 除了根节点外，每个结点有且仅有一个父节点；
  • 一棵N个结点的树，有N-1条边。

一些重要概念：

  • 结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6 ；
  • 树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6；
  • 叶子结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I...等节点为叶结点；
  • 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点；
  • 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点；
  • 根结点：一棵树中，没有双亲结点的结点；如上图：A；
  • 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
  • 树的高度或深度：高度是树中结点的最大层次； 如上图：树的高度为4；深度是针对某一个结点而言的，最大的深度是树的高度；根节点的深度为1表示它是树中最顶层的节点，位于树的第一层。深度是用来描述节点在树中所处的层次位置，根节点的深度为1，它的子节点深度为2，依次类推。深度的概念用于描述节点之间的垂直关系，帮助我们理解树的结构和节点之间的层次关系。

树的以下概念只需了解，在看书时只要知道是什么意思即可：

  • 非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G...等节点为分支结点；
  • 兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点；
  • 堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为堂兄弟结点；
  • 结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先；
  •  子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙；
  • 森林：由m（m>=0）棵互不相交的树组成的集合称为森林。

树的表示形式

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法， 孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。 

1、双亲表示法（Parent Representation）：

  1. class TreeNode {
  2.     int data;
  3.     int parentIndex;
  4. }
  5.  
  6. class ParentTree {
  7.     TreeNode[] nodes;
  8. }

在双亲表示法中，每个节点包含一个指向其父节点的索引。整个树的节点以数组的形式存储，通过索引关系连接节点。

2、孩子表示法（Child Representation）：

  1. class TreeNode {
  2.     int data;
  3.     List<TreeNode> children;
  4. }

 在孩子表示法中，每个节点包含一个指向其子节点的列表。树的结构通过节点之间的引用关系来表示。

3、孩子双亲表示法（Child-Parent Representation）：

  1. class TreeNode {
  2.     int data;
  3.     TreeNode parent;
  4.     List<TreeNode> children;
  5. }

在孩子双亲表示法中，每个节点除了包含指向其子节点的列表外，还包含一个指向其父节点的引用。

4、孩子兄弟表示法（Child-Sibling Representation）：

  1. class TreeNode {
  2.     int data;// 树中存储的数据
  3.     TreeNode parent;
  4.     TreeNode firstChild;// 第一个孩子引用
  5.     TreeNode nextSibling;// 下一个兄弟引用
  6. }

 在孩子兄弟表示法中，每个节点包含指向其第一个子节点和下一个兄弟节点的引用。

树的应用

树的常见应用包括文件系统的表示、数据库索引、组织结构等。

树型结构的特点使得它在表示具有层次关系的数据时非常有用。它提供了一种清晰且灵活的方式来组织和管理数据。树结构的算法和操作通常基于递归的思想，它们可以用来解决许多问题，如搜索、排序、遍历等。树是计算机科学中重要的基础数据结构之一。

二叉树

二叉树是一种特殊的树结构，其中每个节点最多有两个子节点：一个称为左子节点，另一个称为右子节点。

二叉树的定义具有以下特点：

二叉树可以是空的（没有节点），也可以由一个根节点加上左子树和右子树组成。

每个节点最多有两个子节点，即左子节点和右子节点。这意味着每个节点最多可以有两个分支。

左子树和右子树都是二叉树，它们也可以为空。

二叉树的子树之间是相互独立的，即左子树和右子树互不影响。

二叉树的形状可以多样化，它可以是平衡的或不平衡的，可以是满二叉树（每个节点都有两个子节点）或完全二叉树（除了最后一层外，其他层的节点都是满的）。

二叉树在计算机科学中被广泛应用，包括二叉搜索树、堆、表达式树等。

在实现二叉树的代码中，一个二叉树节点通常包含一个值和指向左子节点和右子节点的引用。每个节点通过这些引用形成树的结构。通过递归或迭代的方式，可以对二叉树进行遍历、搜索、插入、删除等操作。二叉树的性质使得它在很多场景下都非常有用，例如在排序、搜索和表示层次结构等方面。

注意：

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

对于任意的二叉树都是由以下几种情况复合而成的：

 两种特殊的二叉树

1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 2 的 k次方 再 -1 (k>=0)，则它就是满二叉树。

2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。即从上到下、从左到右依次存放，而不跳过某个结点。要注意的是满二叉树是一种特殊的完全二叉树。

二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第 i 层上最多（每个结点都存在两个左右孩子）有2 的（i - 1）次方 ( i > 0 )个结点；

2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2 的 k次方 -1 (k>=0)；比如：深度为4的二叉树最多有15结点，2的4次方-1.

3. 对任何一棵二叉树, 如果其叶结点个数为 n0 , 度为2的非叶结点个数为 n2 ,则有 n0＝n2＋1 。即对于任何一棵二叉树，叶子结点的个数永远比度为2的结点的个数多1；怎么得到这个公式的？

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

表达式1：N=n0+n1+n2;

我们刚刚说过：一棵N个结点的树，有N-1条边，度为0的结点向下不会产生边，度为1的结点向下产生1条边，度为2的结点向下产生2条边，所以：

表达式2：N-1=n1 + 2*n2；

联立解得：n0＝n2＋1 。

4. 具有n个结点的完全二叉树的深度k为 log以2为底的(n+1)向上取整（或者 log以2为底的 (n)+1向下取整）；

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有：

  • 若i>0，双亲序号：( i - 1 ) / 2；
  • i = 0，i为根结点编号，无双亲结点；
  • 若2i+1<n，左孩子序号：2 i +1，否则无左孩子；
  • 若2i+2<n，右孩子序号：2 i +2，否则无右孩子；

 了解了性质，我们就要开始做练习了：

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）

A 不存在这样的二叉树

B 200

C 198

D 199

答案：B

解析：对于任何一棵二叉树，叶子结点的个数永远比度为2的结点的个数多1

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

A n

B n+1

C n-1

D n/2

答案：A

解析：对于有偶数个结点的完全二叉树来说：度为1的结点一共有1个。对于奇数个结点的完全二叉树来说，度为1的结点一个0个。这是偶数个结点的二叉树，假设度为0的结点个数为x，n0＝n2＋1 ，所以度为2的结点个数为x-1，所以2n=x+1+x-1，n=x。

3.一个具有767个节点的完全二叉树，其叶子节点个数为（ )

 A 383

B 384

C 385

D 386

答案：B

解析：这题和上面那题差不多，但是这是奇数个结点的二叉树，假设度为0的结点个数为x，n0＝n2＋1 ，所以度为2的结点个数为x-1，所以767=x+x-1，x=384。

4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（ ）

A 11

B 10

C 8

D 12

解析：具有n个结点的完全二叉树的深度k为 log以2为底的(531+1)上取整，2的9次方是512<532；

2的10次方为1024。

5.一颗拥有1000个结点的树度为4，则它的最小深度是（ ）

A.5

B.6

C.7

D.8

答案：B

解析：如果这棵树每一层都是满的，则它的深度最小，所以它是一个四叉树，高度为N，则这个数的节点个数为(4^N - 1) / 3，这里运用的是等差数列求和，当h = 5, 最大节点数为341， 当h = 6, 最大节点数为1365，所以最小深度应该为6。

6.设根结点的深度为1，则一个拥有n个结点的二叉树的深度一定在（   ）区间内

A.[log(n + 1)，n]

B.[logn，n]

C.[log(n + 1)，n - 1]

D.[log(n + 1)，n + 1]

答案：A

解析：

最大深度： 即每次只有一个节点，次数二叉树的高度为n，为最高的高度。

最小深度： 此树为完全二叉树， 如果是完全二叉树，根据二叉树性质，完全二叉树的高低为 h = log以2为底(n+1)向上取整。

二叉树的存储

在学习二叉树的基本操作前，我们需先要创建一棵二叉树，然后才能学习其相关的基本操作。但是由于现在我们对二叉树结构掌握还不够深入，所以我么先手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

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

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

  1. // 孩子表示法
  2. class Node {
  3. int val; // 数据域
  4. Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
  5. Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
  6. }
  7.  
  8. // 孩子双亲表示法
  9. class Node {
  10. int val; // 数据域
  11. Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
  12. Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
  13. Node parent; // 当前节点的根节点
  14. }
  1. public class BinaryTree {
  2.     public static class BTNode{
  3.         BTNode left;
  4.         BTNode right;
  5.         int value;
  6.         BTNode(int value){
  7.             this.value = value;
  8.         }
  9.     }
  10.  
  11.     private BTNode root;// 将来这个引用指向的是根节点
  12.  
  13.     public BTNode createBinaryTree(){
  14.         BTNode node1 = new BTNode(1);
  15.         BTNode node2 = new BTNode(2);
  16.         BTNode node3 = new BTNode(3);
  17.         BTNode node4 = new BTNode(4);
  18.         BTNode node5 = new BTNode(5);
  19.         BTNode node6 = new BTNode(6);
  20.         root = node1;
  21.         node1.left = node2;
  22.         node2.left = node3;
  23.         node1.right = node4;
  24.         node4.left = node5;
  25.         node5.right = node6;
  26.         
  27.         return node1; //这样甚至连头节点都不需要了
  28.     }
  29. }
  30.  
  31. public class Test {
  32.     public static void main(String[] args) {
  33.         BinaryTree binaryTree=new BinaryTree();
  34.         BinaryTree.BTNode ret=binaryTree.createBinaryTree();
  35.         System.out.println("-----------");
  36.     }
  37. }

二叉树的遍历

1. 前中后序遍历

学习二叉树结构，最简单的方式就是遍历。

所谓遍历(Traversal)，是指沿着某条搜索路线，依次对树中每个结 点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加 1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。 

如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。

如果N代表根节点，L代表根节点的 左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：

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

  • 前序遍历结果：1 2 3 4 5 6
  • 中序遍历结果：3 2 1 5 4 6
  • 后序遍历结果：3 1 5 6 4 1

注意：对于每一个结点，都遵循同样的遍历方法。

再做一个简单的练习巩固一下： 

  • 前序遍历结果：A B D E H C F G
  • 中序遍历结果：D B E H A F C G
  • 后序遍历结果：D H E B F G C A

 用代码遍历：

  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.  
  13.         public TreeNode createTree() {
  14.             TreeNode A = new TreeNode('A');
  15.             TreeNode B = new TreeNode('B');
  16.             TreeNode C = new TreeNode('C');
  17.             TreeNode D = new TreeNode('D');
  18.             TreeNode E = new TreeNode('E');
  19.             TreeNode F = new TreeNode('F');
  20.             TreeNode G = new TreeNode('G');
  21.             TreeNode H = new TreeNode('H');
  22.             A.left = B;
  23.             A.right = C;
  24.             B.left = D;
  25.             B.right = E;
  26.             C.left = F;
  27.             C.right = G;
  28.             E.right = H;
  29.             return A;
  30.         }
  31.  
  32.  
  33.         //递归的思想
  34.         //前序遍历
  35.         public void preOrder(TreeNode root){
  36.             if(root==null) return;
  37.             System.out.print(root.val+" ");
  38.             preOrder(root.left);
  39.             preOrder(root.right);
  40.         }
  41.  
  42.         // 中序遍历
  43.         public void inOrder(TreeNode root) {
  44.             if (root == null) {
  45.                 return;
  46.             }
  47.             inOrder(root.left);
  48.             System.out.print(root.val + " ");
  49.             inOrder(root.right);
  50.         }
  51.  
  52.         // 后序遍历
  53.         public void postOrder(TreeNode root) {
  54.             if (root == null) {
  55.                 return;
  56.             }
  57.             postOrder(root.left);
  58.             postOrder(root.right);
  59.             System.out.print(root.val + " ");
  60.         }
  61.  
  62.     }
  1. public class Test {
  2.     public static void main(String[] args) {
  3.         BinaryTree binaryTree = new BinaryTree();
  4.         BinaryTree.TreeNode ret = binaryTree.createTree();
  5.         System.out.println("===");
  6.         System.out.println("前序遍历");
  7.         binaryTree.preOrder(binaryTree.createTree());
  8.         System.out.println();
  9.         System.out.println("中序遍历");
  10.         binaryTree.inOrder(binaryTree.createTree());
  11.         System.out.println();
  12.         System.out.println("后序遍历");
  13.         binaryTree.postOrder(binaryTree.createTree());
  14.         System.out.println();
  15.     }
  16. }

 如果现在要求我们将前序遍历的结果不打印，而是存储到 List 中，怎么实现？

  1.         public List<TreeNode> preOrder2(TreeNode root){
  2.             List<TreeNode> list=new ArrayList<>();
  3.             if(root==null) return list;
  4.             list.add(root);
  5.  
  6.             List<TreeNode> leftTree=preOrder2(root.left);
  7.             list.addAll(leftTree);
  8.  
  9.             List<TreeNode> rightTree=preOrder2(root.right);
  10.             list.addAll(rightTree);
  11.  
  12.             return list;
  13.  
  14.         }
  15.     public List<TreeNode> inOrder2(TreeNode root){
  16.         List<TreeNode> list=new ArrayList<>();
  17.         if(root==null) return list;
  18.  
  19.         List<TreeNode> leftTree=inOrder2(root.left);
  20.         list.addAll(leftTree);
  21.  
  22.         list.add(root);
  23.  
  24.         List<TreeNode> rightTree=inOrder2(root.right);
  25.         list.addAll(rightTree);
  26.         return list;
  27.  
  28.     }
  29.     public List<TreeNode> postOrder2(TreeNode root){
  30.         List<TreeNode> list=new ArrayList<>();
  31.         if(root==null) return list;
  32.  
  33.         List<TreeNode> leftTree=postOrder2(root.left);
  34.         list.addAll(leftTree);
  35.  
  36.         List<TreeNode> rightTree=postOrder2(root.right);
  37.         list.addAll(rightTree);
  38.  
  39.         list.add(root);
  40.         return list;
  41.  
  42.     }
  43.  
  44.  
  45.  
  46.     public static void main(String[] args) {
  47.         BinaryTree binaryTree = new BinaryTree();
  48.         BinaryTree.TreeNode ret = binaryTree.createTree();
  49.         System.out.println("===");
  50.         System.out.println("前序遍历");
  51.         binaryTree.preOrder(binaryTree.createTree());
  52.         System.out.println();
  53.         System.out.println("中序遍历");
  54.         binaryTree.inOrder(binaryTree.createTree());
  55.         System.out.println();
  56.         System.out.println("后序遍历");
  57.         binaryTree.postOrder(binaryTree.createTree());
  58.         System.out.println();
  59.         System.out.println("=================================");
  60.         List<BinaryTree.TreeNode> list =binaryTree.preOrder2(ret);
  61.         for(BinaryTree.TreeNode tree:list){
  62.             System.out.print(tree.val+" ");
  63.         }
  64.         System.out.println();
  65.         System.out.println("=================================");
  66.         List<BinaryTree.TreeNode> list2 =binaryTree.inOrder2(ret);
  67.         for(BinaryTree.TreeNode tree:list2){
  68.             System.out.print(tree.val+" ");
  69.         }
  70.         System.out.println();
  71.         System.out.println("=================================");
  72.         List<BinaryTree.TreeNode> list3 =binaryTree.postOrder2(ret);
  73.         for(BinaryTree.TreeNode tree:list3){
  74.             System.out.print(tree.val+" ");
  75.         }
  76.         System.out.println();
  77.  
  78.     }

2. 层序遍历

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

练习：

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为()

A: ABDHECFG

B: ABCDEFGH

C: HDBEAFCG

D: HDEBFGCA

答案：A

2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为()

A: E

B: F

C: G

D: H

答案：A

解析：根节点就是先序遍历的第一个。如果加大难度，要画出图来，怎么画？

也就是说，我们一定要先通过前序遍历或者后序遍历找根节点，找到根节点之后，我们就去看中序遍历，以根节点为中心然后分左右子树。

分完左右子树后，我们再去看前序遍历或后序遍历的顺序：前者是根左右，后者是左右根。以本题前序遍历为例：

E后面的F就是根节点后面紧跟着的左子树的根。然后现在再回到中序遍历，以F为中心分F的左右子树。我们可以看到，H在F的左边，I在F的右边。

现在看右子树，E后面跳过已经确认过的 F、H、I ，就到了G。G就是根节点的右子树的根。然后现在回到中序遍历，以G为中心分G的左右子树。我们可以看到，J和K都在F的左边，回到前序遍历，发现J紧跟在G的后边，是G的左子树的根。回到中序遍历，K在J的右边，是J的右根。（可能有人会问，为什么K一定是J的右根，而不是G的右根？我们刚刚说过了，K与J都在G的左边，所以都归类于G的左子树。这就代表它们之间是不可能是兄弟节点。）

总之就是两个顺序反复确认，以此类推。

再来一题： 

  3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为()

A: adbce

B: decab

C: debac

D: abcde

答案：D

解析：刚刚是前序和中序，现在是中序和后序。

 那么，根据前序和后序，可以创建一个二叉树吗？

不可以！！！前序和后序只能确认根。没有中序就不可以确认左右。

4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出(同一层从左到右)的序列为()

A: FEDCBA

B: CBAFED

C: DEFCBA

D: ABCDEF

答案：A

解析：只有左子树，没有右子树。

5、二叉树的( )遍历相当于广度优先遍历，( )遍历相当于深度优先遍历 。

（层序遍历）（前序遍历）。

6、如果一颗二叉树的前序遍历的结果是ABCD，则满足条件的不同的二叉树有（ ）种？

A.13

B.14

C.15

D.16

答案：B

二叉树的基本操作

  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4. import java.util.Queue;
  5.  
  6. public class BinaryTree {
  7.         static class TreeNode {
  8.             public int val;
  9.             public TreeNode left;
  10.             public TreeNode right;
  11.  
  12.             public TreeNode(int val) {
  13.                 this.val = val;
  14.             }
  15.         }
  16.  
  17.         private TreeNode root;
  18.         public TreeNode createTree() {
  19.             TreeNode A = new TreeNode('A');
  20.             TreeNode B = new TreeNode('B');
  21.             TreeNode C = new TreeNode('C');
  22.             TreeNode D = new TreeNode('D');
  23.             TreeNode E = new TreeNode('E');
  24.             TreeNode F = new TreeNode('F');
  25.             TreeNode G = new TreeNode('G');
  26.             TreeNode H = new TreeNode('H');
  27.             A.left = B;
  28.             A.right = C;
  29.             B.left = D;
  30.             B.right = E;
  31.             C.left = F;
  32.             C.right = G;
  33.             E.right = H;
  34.             return A;
  35.         }
  36.  
  37.         public void preOrder(TreeNode root){
  38.             if(root==null) return;
  39.             System.out.print(root.val+" ");
  40.             preOrder(root.left);
  41.             preOrder(root.right);
  42.         }
  43.         // 中序遍历
  44.         public void inOrder(TreeNode root) {
  45.             if (root == null) {
  46.                 return;
  47.             }
  48.             inOrder(root.left);
  49.             System.out.print(root.val + " ");
  50.             inOrder(root.right);
  51.         }
  52.  
  53.         // 后序遍历
  54.         public void postOrder(TreeNode root) {
  55.             if (root == null) {
  56.                 return;
  57.             }
  58.             postOrder(root.left);
  59.             postOrder(root.right);
  60.             System.out.print(root.val + " ");
  61.         }
  62.  
  63.         public List<TreeNode> preOrder2(TreeNode root){
  64.             List<TreeNode> list=new ArrayList<>();
  65.             if(root==null) return list;
  66.             list.add(root);
  67.  
  68.             List<TreeNode> leftTree=preOrder2(root.left);
  69.             list.addAll(leftTree);
  70.  
  71.             List<TreeNode> rightTree=preOrder2(root.right);
  72.             list.addAll(rightTree);
  73.  
  74.             return list;
  75.  
  76.         }
  77.     public List<TreeNode> inOrder2(TreeNode root){
  78.         List<TreeNode> list=new ArrayList<>();
  79.         if(root==null) return list;
  80.  
  81.         List<TreeNode> leftTree=inOrder2(root.left);
  82.         list.addAll(leftTree);
  83.  
  84.         list.add(root);
  85.  
  86.         List<TreeNode> rightTree=inOrder2(root.right);
  87.         list.addAll(rightTree);
  88.         return list;
  89.  
  90.     }
  91.     public List<TreeNode> postOrder2(TreeNode root){
  92.         List<TreeNode> list=new ArrayList<>();
  93.         if(root==null) return list;
  94.  
  95.         List<TreeNode> leftTree=postOrder2(root.left);
  96.         list.addAll(leftTree);
  97.  
  98.         List<TreeNode> rightTree=postOrder2(root.right);
  99.         list.addAll(rightTree);
  100.  
  101.         list.add(root);
  102.         return list;
  103.  
  104.     }
  105.  
  106.     // 获取树中节点的个数
  107.  
  108.     //以 前/中/后序 遍历这棵树的时候，会把每个节点都遍历到。遍历一个节点就计数一次
  109.     //较笨拙的方法——遍历的思想
  110.     public void size1(TreeNode root) {
  111.         if (root == null) {
  112.             return;
  113.         }
  114.         int size=0;
  115.         size++;
  116.         size1(root.left);
  117.         size1(root.right);
  118.     }
  119.     //改进
  120.     public int size2(TreeNode root) {
  121.         if (root == null) {
  122.             return 0;
  123.         } else {
  124.             return 1 + size2(root.left) + size2(root.right);
  125.         }
  126.     }
  127.  
  128.  
  129.  
  130.     // 获取叶子节点的个数
  131.     //遍历的思想
  132.     public void getLeafNodeCount1(TreeNode root) {
  133.             int leafsize=0;
  134.         if (root == null) {
  135.             return ;
  136.         }
  137.  
  138.         if (root.left == null && root.right == null) {
  139.             leafsize++;
  140.         }
  141.  
  142.         getLeafNodeCount1(root.left);
  143.         getLeafNodeCount1(root.right);
  144.  
  145.     }
  146.  
  147.     //进阶  root左树的叶子+root右树的叶子=整棵树的叶子
  148.  
  149.     public int getLeafNodeCount2(TreeNode root) {
  150.         if (root == null) {
  151.             return 0;
  152.         } else if (root.left == null && root.right == null) {
  153.             return 1;
  154.         } else {
  155.             return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
  156.         }
  157.     }
  158.  
  159.  
  160.     // 获取第K层节点的个数
  161.     //root这棵树的第K层=root.left的第k-1层+root.right的第k-1层
  162.     //以此类推直到k=1
  163.     public int getKLevelNodeCount(TreeNode root, int k) {
  164.         if (root == null || k < 1) {
  165.             return 0;
  166.         } else if (k == 1) {
  167.             return 1;
  168.         } else {
  169.             return getKLevelNodeCount(root.left, k - 1) +
  170.                     getKLevelNodeCount(root.right, k - 1);
  171.         }
  172.     }
  173.  
  174.     // 获取二叉树的高度
  175.     public int getHeight(TreeNode root) {
  176.         if (root == null) {
  177.             return 0;
  178.         } else {
  179.             int leftHeight = getHeight(root.left);
  180.             int rightHeight = getHeight(root.right);
  181.             return Math.max(leftHeight, rightHeight) + 1;
  182.         }
  183.     }
  184.     public int getHeight2(TreeNode root) {
  185.         if (root == null) {
  186.             return 0;
  187.         } else {
  188.             int leftHeight = getHeight(root.left);
  189.             int rightHeight = getHeight(root.right);
  190.             return leftHeight > rightHeight ? leftHeight+ 1 : rightHeight+1;
  191.         }
  192.     }
  193.  
  194.     
  195.     // 检测值为value的元素是否存在
  196.     public TreeNode find(TreeNode root, int val) {
  197.         if (root == null || root.val == val) {
  198.             return root;
  199.         } else {
  200.             TreeNode leftResult = find(root.left, val);
  201.             TreeNode rightResult = find(root.right, val);
  202.             if (leftResult != null) {
  203.                 return leftResult;
  204.             } else {
  205.                 return rightResult;
  206.             }
  207.         }
  208.     }
  209.  
  210.     // 层序遍历
  211.     public void levelOrder(TreeNode root) {
  212.         if (root == null) {
  213.             return;
  214.         }
  215.  
  216.         Queue<TreeNode> queue = new LinkedList<>();
  217.         queue.offer(root);
  218.  
  219.         while (!queue.isEmpty()) {
  220.             TreeNode node = queue.poll();
  221.             System.out.print(node.val + " ");
  222.  
  223.             if (node.left != null) {
  224.                 queue.offer(node.left);
  225.             }
  226.  
  227.             if (node.right != null) {
  228.                 queue.offer(node.right);
  229.             }
  230.         }
  231.     }
  232.  
  233.     // 判断一棵树是不是完全二叉树
  234.     // 一棵完全二叉树，层序遍历时已经遇到了null，那么后面的所有节点都为null
  235.     // null算一个元素，即使队列里面全是null，它也不为空
  236.     public boolean isCompleteTree(TreeNode root) {
  237.         if (root == null) {
  238.             return true;
  239.         }
  240.  
  241.         Queue<TreeNode> queue = new LinkedList<>();
  242.         queue.offer(root);
  243.  
  244.         boolean flag = false; // 标志位，用于判断是否遇到了非完全节点
  245.  
  246.         while (!queue.isEmpty()) {
  247.             TreeNode node = queue.poll();
  248.  
  249.             if (node.left != null) {
  250.                 if (flag) {
  251.                     return false; // 遇到非完全节点后，如果还有子节点，则不是完全二叉树
  252.                 }
  253.                 queue.offer(node.left);
  254.             } else {
  255.                 flag = true; // 遇到了非完全节点
  256.             }
  257.  
  258.             if (node.right != null) {
  259.                 if (flag) {
  260.                     return false; // 遇到非完全节点后，如果还有子节点，则不是完全二叉树
  261.                 }
  262.                 queue.offer(node.right);
  263.             } else {
  264.                 flag = true; // 遇到了非完全节点
  265.             }
  266.         }
  267.  
  268.         return true;
  269.     }
  270.  
  271.     public static void main(String[] args) {
  272.         BinaryTree binaryTree = new BinaryTree();
  273.  
  274.         // 构造二叉树
  275.         binaryTree.root = new TreeNode(1);
  276.         binaryTree.root.left = new TreeNode(2);
  277.         binaryTree.root.right = new TreeNode(3);
  278.         binaryTree.root.left.left = new TreeNode(4);
  279.         binaryTree.root.left.right = new TreeNode(5);
  280.         binaryTree.root.right.left = new TreeNode(6);
  281.         binaryTree.root.right.right = new TreeNode(7);
  282.  
  283.         // 测试各个操作
  284.         System.out.println("树中节点的个数: " + binaryTree.size2(binaryTree.root));
  285.         System.out.println("叶子节点的个数: " + binaryTree.getLeafNodeCount2(binaryTree.root));
  286.         System.out.println("第3层节点的个数: " + binaryTree.getKLevelNodeCount(binaryTree.root, 3));
  287.         System.out.println("二叉树的高度: " + binaryTree.getHeight(binaryTree.root));
  288.         System.out.println("值为5的元素是否存在: " + (binaryTree.find(binaryTree.root, 5) != null));
  289.         System.out.println("层序遍历: ");
  290.         binaryTree.levelOrder(binaryTree.root);
  291.         System.out.println("\n是否完全二叉树: " + binaryTree.isCompleteTree(binaryTree.root));
  292.     }
  293. }

判断是否为完全二叉树的另一种写法：

  1.     public boolean isCompleteTree(TreeNode root) {
  2.         if(root == null) {
  3.             return true;
  4.         }
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         queue.offer(root);
  7.         while (!queue.isEmpty()) {
  8.             TreeNode cur = queue.poll();
  9.             if(cur != null) {
  10.                 queue.offer(cur.left);
  11.                 queue.offer(cur.right);
  12.             }else {
  13.                 //此时遇到了null
  14.                 break;
  15.             }
  16.         }
  17.         while (!queue.isEmpty()) {
  18.             TreeNode cur = queue.poll();
  19.             if(cur != null) {
  20.                 return false;
  21.             }
  22.         }
  23.         return true;
  24.     }

二叉树相关的 OJ 题

1. 检查两颗树是否相同

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

力扣：100. 相同的树 - 力扣（Leetcode）

  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 boolean isSameTree(TreeNode p, TreeNode q) {
  18.         // 如果两个树都为空，它们相同
  19.         if (p == null && q == null) {
  20.             return true;
  21.         }
  22.         // 如果只有一个树为空，它们不相同
  23.         if (p != null && q == null || p == null && q != null) {
  24.             return false;
  25.         }
  26.         // 如果根节点的值不相等，它们不相同
  27.         if (p.val != q.val) {
  28.             return false;
  29.         }
  30.         // 递归比较左子树和右子树
  31.         return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  32.     }
  33. }

 首先，它检查两棵树是否都为空，如果是，则它们相同。然后，它检查如果只有一棵树为空，那么它们不相同。接下来，它比较根节点的值，如果不相等，则它们不相同。最后，它递归地比较左子树和右子树。如果左右子树都相同，那么整棵树相同。这个方法会递归地在树的每个节点上执行相同的比较操作。

这段代码的时间复杂度是O(min(N, M)),其中N和M分别表示两个输入树的节点数量。

在每个递归步骤中，我们比较了两个节点的值，并且进行了递归调用以比较左子树和右子树。在最坏的情况下，我们需要比较两个树的所有节点。

如果两个树的节点数量不同，我们将在较小的树上完成比较，因此时间复杂度是O(min(N, M))。

但是 ,  上述代码的时间复杂度分析基于一个假设：每次比较两个节点的值和递归调用的开销都是常数时间。这意味着我们假设节点的比较和递归调用所需的时间与输入规模无关，即不随着节点数量的增加而增加。

然而，这个假设忽略了树的形状对递归调用次数的影响。如果两个树的形状不平衡，即节点的排列方式导致递归调用的次数较多，那么时间复杂度可能会增加。

例如，如果其中一个树是一个链表形式的树（所有节点都只有右子节点或只有左子节点），而另一个树是一个平衡的完全二叉树，那么递归调用的次数将取决于链表形式的树的节点数量，而不是最小节点数量。

因此，上述时间复杂度分析中的假设适用于平衡树或具有类似形状的树，而对于不平衡的树，时间复杂度可能会因形状而异。

2. 另一颗树的子树

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

力扣：https://leetcode.cn/problems/subtree-of-another-tree/

  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 boolean isSubtree(TreeNode root, TreeNode subRoot) {
  18.         if (root == null) {
  19.             return false;
  20.         }
  21.         if (isSameTree(root, subRoot)) {
  22.             return true;
  23.         }
  24.         return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
  25.     }
  26.     
  27.     private boolean isSameTree(TreeNode p, TreeNode q) {
  28.         if (p == null && q == null) {
  29.             return true;
  30.         }
  31.         if (p != null && q == null || p == null && q != null ) {
  32.             return false;
  33.         }
  34.         if (p.val != q.val) {
  35.             return false;
  36.         }
  37.         return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  38.     }
  39. }

该方法isSubtree首先检查root是否为空，如果为空，则返回false。然后，它调用isSameTree方法来比较root和subRoot是否相同。如果相同，则返回true。如果不同，则递归地在root的左子树和右子树中继续查找subRoot。如果左子树或右子树中存在与subRoot相同的子树，则返回true。如果遍历完整棵树后仍未找到相同的子树，则返回false。

isSameTree方法是之前回答中的相同树比较方法，用于判断两棵树是否在结构上相同且节点值相同。

这段代码的时间复杂度是O(N*M)，其中N是树root的节点数，M是树subRoot的节点数。

3. 翻转二叉树

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

这题该怎么理解？我们应该从最底层的叶子节点开始交换，自下而上翻转。每一棵子树都交换左右孩子的指向，遍历这棵二叉树的每一个节点。

力扣：226. 翻转二叉树 - 力扣（Leetcode）

  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 TreeNode invertTree(TreeNode root) {
  18.         if (root == null) {
  19.             return null;
  20.         }
  21.         // 递归地翻转左右子树
  22.         TreeNode left = invertTree(root.left);
  23.         TreeNode right = invertTree(root.right);
  24.         // 交换左右子树
  25.         root.left = right;
  26.         root.right = left;
  27.         return root;
  28.     }
  29.  
  30.     public TreeNode invertTree2 (TreeNode root) {
  31.         if (root == null) {
  32.             return null;
  33.         }
  34.         TreeNode tmp=root.left;
  35.         root.left=root.right;
  36.         root.right=tmp;
  37.         // 递归地翻转左右子树
  38.         invertTree(root.left);
  39.         invertTree(root.right);
  40.  
  41.         return root;
  42.     }
  43. }

该方法invertTree首先检查根节点是否为空，如果为空，则返回null。然后，它递归地翻转左子树和右子树，将返回的翻转后的左子树和右子树赋值给根节点的右子树和左子树。最后，返回根节点，完成整棵二叉树的翻转。

 我们通过递归地在每个节点上执行相同的翻转操作，可以实现对整棵二叉树的翻转。

这段代码的时间复杂度是O(N)，其中N表示输入树的节点数量。

在这段代码中，我们使用递归的方式遍历每个节点，并在每个节点上进行左右子树的翻转。对于每个节点，我们都进行了常数时间的交换操作。

在最坏的情况下，我们需要遍历树的每个节点，因此时间复杂度是O(N)。注意，这个时间复杂度假设节点的交换操作是常数时间，而不考虑树的形状。

类似于之前的问题，如果树的形状不平衡，即节点的排列方式导致递归调用的次数较多，时间复杂度可能会变得更高。但是，对于每个节点，我们只执行常数时间的交换操作，因此整体的时间复杂度仍然是O(N)。

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

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

 力扣：110. 平衡二叉树 - 力扣（Leetcode）

  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 boolean isBalanced(TreeNode root) {
  18.         if (root == null) {
  19.             return true;
  20.         }
  21.         // 检查当前节点的左右子树的高度差是否超过1
  22.         if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
  23.             return false;
  24.         }
  25.         // 递归地检查左子树和右子树是否都是高度平衡的
  26.         return isBalanced(root.left) && isBalanced(root.right);
  27.     }
  28.     
  29.     private int getHeight(TreeNode node) {
  30.         if (node == null) {
  31.             return 0;
  32.         }
  33.         // 递归地计算节点的高度
  34.         int leftHeight = getHeight(node.left);
  35.         int rightHeight = getHeight(node.right);
  36.         // 返回节点的高度（左右子树中较大的高度加上1）
  37.         return Math.max(leftHeight, rightHeight) + 1;
  38.         /*return (leftHeight>rightHeight?leftHeight+1:rightHeight+1);*/
  39.     }
  40. }

该方法isBalanced首先检查根节点是否为空，如果为空，则认为它是高度平衡的。然后，它检查当前节点的左右子树的高度差是否超过1。如果超过1，则返回false。如果未超过1，则递归地检查左子树和右子树是否都是高度平衡的。其中，getHeight方法用于递归地计算节点的高度。对于空节点，高度为0；对于非空节点，高度为左右子树中较大的高度加上1。 

这样，通过递归地在每个节点上执行高度平衡检查，可以判断一棵二叉树是否是高度平衡的。

但是这样，我们的代码会有一个问题——不停的重复计算导致的效率低下。

如此，这段代码的时间复杂度就会是O(N^2)，其中N表示输入树的节点数量。

在isBalanced方法中，我们首先检查当前节点的左右子树的高度差是否超过1，这需要O(1)的时间。然后，我们递归地调用isBalanced方法来检查左子树和右子树是否都是高度平衡的。

在getHeight方法中，我们首先递归地计算节点的左子树和右子树的高度，这会消耗O(N)的时间，因为在最坏的情况下，需要遍历树的所有节点。然后，我们返回节点的高度，这需要O(1)的时间。

由于在isBalanced方法中的每个节点上都调用了getHeight方法，且每次调用getHeight都需要O(N)的时间，所以整体的时间复杂度是O(N^2)。

这是因为在最坏的情况下，对于每个节点，我们都需要遍历树的所有节点来计算高度，而在判断平衡性时，我们对每个节点都进行了一次高度计算。因此，整体的时间复杂度是二者的乘积，即O(N * N) = O(N^2)。

能否在求高度的过程中，就能知道这棵树平衡与否？

如果getHeight方法的结果被缓存起来，我们就可以避免重复计算，从而将时间复杂度降低到O(N)。

  1. import java.util.HashMap;
  2. import java.util.Map;
  3.  
  4. class Solution {
  5.     public boolean isBalanced(TreeNode root) {
  6.         if (root == null) {
  7.             return true;
  8.         }
  9.         
  10.         // 使用缓存来存储节点的高度
  11.         Map<TreeNode, Integer> heightMap = new HashMap<>();
  12.         
  13.         return isBalancedHelper(root, heightMap);
  14.     }
  15.     
  16.     private boolean isBalancedHelper(TreeNode node, Map<TreeNode, Integer> heightMap) {
  17.         if (node == null) {
  18.             return true;
  19.         }
  20.         
  21.         // 检查缓存中是否已经存储了节点的高度
  22.         if (heightMap.containsKey(node)) {
  23.             return heightMap.get(node) != -1; // 高度为-1表示节点不平衡
  24.         }
  25.         
  26.         // 递归地检查左子树和右子树是否都是高度平衡的
  27.         boolean leftBalanced = isBalancedHelper(node.left, heightMap);
  28.         boolean rightBalanced = isBalancedHelper(node.right, heightMap);
  29.         
  30.         // 计算节点的高度并存储到缓存中
  31.         int leftHeight = getHeight(node.left, heightMap);
  32.         int rightHeight = getHeight(node.right, heightMap);
  33.         int currentHeight = Math.max(leftHeight, rightHeight) + 1;
  34.         heightMap.put(node, currentHeight);
  35.         
  36.         // 检查当前节点的左右子树的高度差是否超过1
  37.         if (Math.abs(leftHeight - rightHeight) > 1) {
  38.             return false;
  39.         }
  40.         
  41.         return leftBalanced && rightBalanced;
  42.     }
  43.     
  44.     private int getHeight(TreeNode node, Map<TreeNode, Integer> heightMap) {
  45.         if (node == null) {
  46.             return 0;
  47.         }
  48.         
  49.         // 检查缓存中是否已经存储了节点的高度
  50.         if (heightMap.containsKey(node)) {
  51.             return heightMap.get(node);
  52.         }
  53.         
  54.         // 递归地计算节点的高度
  55.         int leftHeight = getHeight(node.left, heightMap);
  56.         int rightHeight = getHeight(node.right, heightMap);
  57.         
  58.         // 计算节点的高度并存储到缓存中
  59.         int currentHeight = Math.max(leftHeight, rightHeight) + 1;
  60.         heightMap.put(node, currentHeight);
  61.         
  62.         return currentHeight;
  63.     }
  64. }

这段修改后的代码使用了一个heightMap来缓存每个节点的高度，避免重复计算。在每次需要获取节点高度时，首先检查缓存中是否已经存在该节点的高度，如果存在则直接返回。如果不存在，则进行递归计算并将计算结果存储到缓存中。

这样，在判断节点平衡性时，每个节点的高度只需要计算一次，然后从缓存中获取即可，避免了重复计算。这样，整体的时间复杂度可以降低到O(N)，其中N表示节点的数量。

或者不用哈希表，这样也可以：

  1.     public boolean isBalanced(TreeNode root) {
  2.  
  3.         if (root == null) {
  4.             return true;
  5.         }
  6.  
  7.         return getHeight(root)>=0;
  8.     }
  9.  
  10.     private int getHeight(TreeNode node) {
  11.  
  12.         if (node == null) {
  13.             return 0;
  14.         }
  15.  
  16.         // 递归地计算节点的高度
  17.         int leftHeight = getHeight(node.left);
  18.         int rightHeight = getHeight(node.right);
  19.  
  20.         if(leftHeight >= 0 && rightHeight >= 0 && 
  21.            Math.abs(leftHeight-rightHeight) <= 1 ){
  22.             return Math.max(leftHeight,rightHeight)+1;
  23.         }else {
  24.             return -1;
  25.         }
  26.     }

在该方法中，如果发现子树在任何点不平衡getHeight，它就会返回，而不是将高度存储在缓存中。

也就是说，如果左右子树都是平衡的，并且它们之间的高度差小于或等于1，则计算并返回最大高度加1。而如果不平衡，那么就会返回-1。这种方法利用哨兵值（即标志值或特殊值）通过递归向上传播不平衡-1状态。

然后isBalanced方法检查返回的高度是否getHeight为非负数(表示平衡子树)并相应地返回结果。这种方法通过在检测到不平衡子树时立即终止递归来避免冗余计算。

因此，修改后的代码有效地避免了冗余计算并达到了预期的优化，导致时间复杂度为O(N)，其中N表示树中的节点数量。

很有意思的一个方法，不是吗？

5. 对称二叉树

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

力扣：101. 对称二叉树 - 力扣（Leetcode） 

  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 boolean isSymmetric(TreeNode root) {
  18.         if (root == null) {
  19.             return true;
  20.         }
  21.         return isMirror(root.left, root.right);
  22.     }
  23.     
  24.     private boolean isMirror(TreeNode left, TreeNode right) {
  25.         if (left == null && right == null) {
  26.             return true;
  27.         }
  28.         if (left==null && right!=null || right==null && left!=null 
  29.             || left.val != right.val) {
  30.             return false;
  31.         }
  32.         /*if (left==null || right==null
  33.             || left.val != right.val) {
  34.             return false;
  35.         }*/
  36.         return isMirror(left.left, right.right) && isMirror(left.right, right.left);
  37.     }
  38. }

该方法isSymmetric首先检查根节点是否为空，如果为空，则认为它是轴对称的。然后，它调用isMirror方法来判断左子树和右子树是否是镜像对称的。isMirror方法中，它首先检查左右节点是否同时为空，如果是，则认为它们是镜像对称的。然后，它检查左右节点是否有一个为空或者值不相等，如果是，则认为它们不是镜像对称的。最后，它递归地判断左子树的左节点和右子树的右节点是否是镜像对称的，并且判断左子树的右节点和右子树的左节点是否是镜像对称的。如果左右子树都是镜像对称的，那么整棵树是轴对称的。

通过递归地在每个节点上执行镜像对称性检查，可以判断一棵二叉树是否是轴对称的。

该代码的时间复杂度是 O(N)，其中 N 是二叉树中的节点数量。

6. 二叉树的构建及遍历

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储，说明是链式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

牛客：二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

  1. import java.util.Scanner;
  2.  
  3.     static class TreeNode {
  4.         char val;
  5.         TreeNode left;
  6.         TreeNode right;
  7.  
  8.         TreeNode(char val) {
  9.             this.val = val;
  10.         }
  11.     }
  12.  
  13.  
  14.         private static int index = 0;
  15.  
  16.         public static void main(String[] args) {
  17.             Scanner in = new Scanner(System.in);
  18.             while (in.hasNextLine()) {  // 循环读取输入的每一行
  19.                 String preorder = in.nextLine();  // 读取先序遍历字符串
  20.                 TreeNode root = buildTree(preorder);  // 构建二叉树
  21.                 String inorder = inorderTraversal(root);  // 中序遍历二叉树
  22.                 System.out.println(inorder);  // 打印中序遍历结果
  23.             }
  24.         }
  25.  
  26.         private static TreeNode buildTree(String preorder) {
  27.             index = 0;  // 重置索引为0
  28.             return buildTreeHelper(preorder);  // 调用辅助方法构建二叉树
  29.         }
  30.  
  31.         private  static  TreeNode buildTreeHelper(String preorder) {
  32.             if (index >= preorder.length()) {  // 如果索引超出字符串长度，表示已遍历完，返回null
  33.                 return null;
  34.             }
  35.  
  36.             char ch = preorder.charAt(index++);  // 获取当前字符，并将索引增加1
  37.             if (ch == '#') {  // 如果当前字符是'#'，表示是空节点，返回null
  38.                 return null;
  39.             }
  40.  
  41.             TreeNode node = new TreeNode(ch);  // 创建新的二叉树节点
  42.             node.left = buildTreeHelper(preorder);  // 递归构建左子树
  43.             node.right = buildTreeHelper(preorder);  // 递归构建右子树
  44.  
  45.             return node;  // 返回构建好的节点
  46.         }
  47.  
  48.         private static String inorderTraversal(TreeNode root) {
  49.             StringBuilder sb = new StringBuilder();  // 创建StringBuilder对象，用于保存中序遍历结果
  50.             inorderTraversalHelper(root, sb);  // 调用辅助方法进行中序遍历
  51.             return sb.toString();  // 返回中序遍历结果的字符串形式
  52.         }
  53.  
  54.         private static void inorderTraversalHelper(TreeNode node, StringBuilder sb) {
  55.             if (node == null) {  // 如果节点为空，表示到达叶子节点，直接返回
  56.                 return;
  57.             }
  58.  
  59.             inorderTraversalHelper(node.left, sb);  // 递归遍历左子树
  60.             sb.append(node.val).append(" ");  // 将当前节点值添加到结果中
  61.             inorderTraversalHelper(node.right, sb);  // 递归遍历右子树
  62.         }

这个程序首先读取用户输入的一串先序遍历字符串。然后使用buildTree函数根据该字符串建立二叉树，并使用inorderTraversal函数进行中序遍历。buildTree函数使用递归的方式构建二叉树，每次取出字符串中的一个字符，如果是#表示空树，则返回null，否则创建一个新的节点，并递归构建其左子树和右子树。inorderTraversal函数使用递归的方式进行中序遍历，先遍历左子树，然后将当前节点的值添加到结果字符串中，最后遍历右子树。

通过这个程序，可以根据输入的先序遍历字符串建立二叉树，并输出中序遍历的结果。每个字符后面都有一个空格，每个输出结果占一行。

那么如果我们根据前序遍历来做这个题，即前序遍历的过程中顺便通过前序遍历构建二叉树，而不是用index来确定循环次数，该怎么办？如下：

  1. import java.util.Scanner;
  2.  
  3. // 注意类名必须为 Main, 不要有任何 package xxx 信息
  4.  
  5. class TreeNode {
  6.     char val;
  7.     TreeNode left;
  8.     TreeNode right;
  9.  
  10.     TreeNode(char val) {
  11.         this.val = val;
  12.     }
  13. }
  14.  
  15. public class Main {
  16.     // 注意类名必须为 Main，不要有任何 package xxx 信息 public class Main {
  17.     public static void main(String[] args) {
  18.         Scanner in = new Scanner(System.in);// 注意hasNext 和hasNextLine的区别
  19.         while (in.hasNextLine()) { // 注意 while 处理多个 case
  20.             String str = in.nextLine();
  21.             TreeNode root = creatrTree(str);
  22.             inorder(root);
  23.         }
  24.     }
  25.  
  26.     public static  int i = 0;
  27.  
  28.     public static TreeNode creatrTree(String str) {
  29.         TreeNode root = null;
  30.  
  31.         if (str.charAt(i) != '#') {
  32.             root = new TreeNode(str.charAt(i));
  33.             i++;
  34.             root.left = creatrTree(str);
  35.             root.right = creatrTree(str);
  36.         } else {
  37.             i++;
  38.         }
  39.         return root;
  40.     }
  41.  
  42.  
  43.  
  44. public static void inorder(TreeNode root) {
  45.     if (root == null) {
  46.         return;
  47.     }
  48.     inorder(root.left);
  49.     System.out.print(root.val + " ");
  50.     inorder(root.right);
  51.  
  52.     }
  53. }

我们并不用考虑，i 是否会越界的情况，因为我们根本没有用 i 来控制循环次数，而是一边前序遍历，一边构建整棵树。

建议你自己顺着代码理一遍，画一次图。

当然，如果我们设置 i 为静态变量，那么它只适用于一个测试用例，如果有多个测试用例，那么可能无法正常运行（这也就是为什么有时候这种代码在牛课可以通过，在力扣就通不过，或者在IDEA就OK，别的不行的原因）。所以最好的，我们要把 static 去掉，这样即使有多个测试用例，也可以得到正确结果。

7. 二叉树的分层遍历

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

力扣：102. 二叉树的层序遍历 - 力扣（Leetcode）

  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4. import java.util.Queue;
  5.  
  6. class TreeNode {
  7.     int val;
  8.     TreeNode left;
  9.     TreeNode right;
  10.     
  11.     TreeNode(int val) {
  12.         this.val = val;
  13.     }
  14. }
  15.  
  16. class Solution {
  17.     public List<List<Integer>> levelOrder(TreeNode root) {
  18.         List<List<Integer>> result = new ArrayList<>();
  19.         if (root == null) {
  20.             return result;  //注意，这里如果给的是[]，那么你也要返回[]，而不是null
  21.         }
  22.         
  23.         Queue<TreeNode> queue = new LinkedList<>();
  24.         queue.offer(root);
  25.         
  26.         while (!queue.isEmpty()) {
  27.             int levelSize = queue.size();
  28.             List<Integer> levelValues = new ArrayList<>();
  29.             
  30.             for (int i = 0; i < levelSize; i++) {
  31.                 TreeNode node = queue.poll();
  32.                 levelValues.add(node.val);
  33.                 
  34.                 if (node.left != null) {
  35.                     queue.offer(node.left);
  36.                 }
  37.                 
  38.                 if (node.right != null) {
  39.                     queue.offer(node.right);
  40.                 }
  41.             }
  42.             
  43.             result.add(levelValues);
  44.         }
  45.         
  46.         return result;
  47.     }
  48. }

在levelOrder函数中，我们首先创建一个结果列表result来存储层序遍历的结果。然后，我们创建一个队列queue并将根节点入队。接下来，我们使用一个循环来处理每一层的节点。在循环中，我们首先获取当前层的节点数levelSize，然后创建一个列表levelValues来存储当前层的节点值。接着，我们从队列中取出levelSize个节点，将它们的值加入levelValues列表，并将它们的非空子节点加入队列。完成当前层的处理后，我们将levelValues列表加入result列表。最终，当队列为空时，我们完成了二叉树的层序遍历。

通过这个程序，可以获得二叉树节点值的层序遍历结果，并将其存储在一个列表中返回。每个层的节点值都存储在独立的列表中，按层级顺序排列。

非常相似的写法，可以先理解前面的部分，在拓展到 List<List<TreeNode>> 的部分：

  1.     public void levelOrder1(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();
  9.             System.out.print(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.     }
  18.  
  19.     public List<List<TreeNode>> levelOrder(TreeNode root) {
  20.         List<List<TreeNode>> ret = new ArrayList<>();
  21.         if(root == null) {
  22.             return ret;
  23.         }
  24.         Queue<TreeNode> queue = new LinkedList<>();
  25.         queue.offer(root);
  26.         while (!queue.isEmpty()) {
  27.             //求一下当前队列的大小  4
  28.             int size = queue.size();//4
  29.             List<TreeNode> tmp = new ArrayList<>();
  30.             while (size != 0) {
  31.                 // 出队列4次 相当于把 这一层的节点都 出队了
  32.                 TreeNode cur = queue.poll();
  33.                 //System.out.print(cur.val+" ");
  34.                 tmp.add(cur);
  35.                 size--;//0
  36.                 if(cur.left != null) {
  37.                     queue.offer(cur.left);
  38.                 }
  39.                 if(cur.right != null) {
  40.                     queue.offer(cur.right);
  41.                 }
  42.             }
  43.             ret.add(tmp);
  44.         }
  45.         return ret;
  46.     }

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

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

力扣：236. 二叉树的最近公共祖先 - 力扣（Leetcode）

我们当然可以利用之前写过的判断是否为子树的方法来做这道题，同样也要用到递归的思想：

  1. class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
  3.         if(root==null||p==null||q==null){
  4.             return null;
  5.         }
  6.         if(p==root||q==root){
  7.             return root;
  8.         }
  9.     if (isSubtree(root.left, p) && isSubtree(root.left, q)) {
  10.         return lowestCommonAncestor(root.left, p, q);
  11.     }
  12.     if (isSubtree(root.right, p) && isSubtree(root.right, q)) {
  13.         return lowestCommonAncestor(root.right, p, q);
  14.     }
  15.     return root;
  16.     }
  17.  
  18.     public boolean isSubtree(TreeNode root, TreeNode subRoot) {
  19.         if (root == null) {
  20.             return false;
  21.         }
  22.         if (isSameTree(root, subRoot)) {
  23.             return true;
  24.         }
  25.         return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
  26.     }
  27.  
  28.     private boolean isSameTree(TreeNode p, TreeNode q) {
  29.         if (p == null && q == null) {
  30.             return true;
  31.         }
  32.         if (p == null || q == null) {
  33.             return false;
  34.         }
  35.         if (p.val != q.val) {
  36.             return false;
  37.         }
  38.         return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  39.     }
  40. }

但是这个方法的时间复杂度太大了： 

所以我们换个思路： 

或者借助二叉搜索树（根节点的左边都比根小；根节点的右边都比根大）的性质来思考。

  1. class TreeNode {
  2.     int val;
  3.     TreeNode left;
  4.     TreeNode right;
  5.     
  6.     TreeNode(int x) {
  7.         val = x;
  8.     }
  9. }
  10.  
  11. class Solution {
  12.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  13.         if (root == null || root == p || root == q) {
  14.             return root;
  15.         }
  16.         
  17.         TreeNode left = lowestCommonAncestor(root.left, p, q);
  18.         TreeNode right = lowestCommonAncestor(root.right, p, q);
  19.         
  20.         if (left != null && right != null) {
  21.             return root;
  22.         } else if (left != null) {
  23.             return left;
  24.         } else {
  25.             return right;
  26.         }
  27.     }
  28. }

在lowestCommonAncestor函数中，我们首先检查当前节点是否为空或等于节点p或节点q。如果是，那么当前节点就是最近公共祖先，我们直接返回该节点。否则，我们分别在左子树和右子树中递归寻找最近公共祖先。如果左子树和右子树都返回非空节点，那么说明节点p和节点q分别在当前节点的左子树和右子树中，当前节点就是最近公共祖先。如果只有左子树返回非空节点，那么说明节点p和节点q都在左子树中，返回左子树的结果作为最近公共祖先。如果只有右子树返回非空节点，那么说明节点p和节点q都在右子树中，返回右子树的结果作为最近公共祖先。

这个写法不太好理解，我建议你最好自己画一个图来感受，并且把p和q放到不同的位置来进行多次判断。 

通过这个程序，我们就可以找到二叉树中两个指定节点的最近公共祖先，并将其作为结果返回。

还有没有别的解法？再介绍一种：

如果二叉树可以保存父亲节点的地址，那么这个题可以转变为——求链表的相交节点。

把p、q的路径分别存放到2个栈里面，先计算一下路径节点的个数，把差值个数去掉，然后同时弹出剩余节点并比较，如果相等，则该节点即为公共祖先。

 这道题最大的难度是：如何找到根节点到指定节点路径上的所有节点：

  1.     private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
  2.         if(root == null || node == null) {
  3.             return false;
  4.         }
  5.         stack.push(root);
  6.         if(root == node) {
  7.             return true;
  8.         }
  9.         boolean flg = getPath(root.left,node,stack);
  10.         if(flg) {
  11.             return true;
  12.         }
  13.         boolean flg2 = getPath(root.right,node,stack);
  14.         if(flg2) {
  15.             return true;
  16.         }
  17.         stack.pop();
  18.         return false;
  19.     }
  20.

接下来的就比较好写了：

  1.     public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
  2.         if(root == null) {
  3.             return null;
  4.         }
  5.         //定义两个栈
  6.         Stack<TreeNode> stackP = new Stack<>();
  7.         Stack<TreeNode> stackQ = new Stack<>();
  8.  
  9.         getPath(root,p,stackP);
  10.         getPath(root,q,stackQ);
  11.  
  12.         //对栈的操作
  13.         int sizeP = stackP.size();
  14.         int sizeQ = stackQ.size();
  15.  
  16.         if(sizeP > sizeQ) {
  17.             int size = sizeP - sizeQ;
  18.             while (size != 0) {
  19.                 stackP.pop();
  20.                 size--;
  21.             }
  22.         }else {
  23.             int size = sizeQ - sizeP;
  24.             while (size != 0) {
  25.                 stackQ.pop();
  26.                 size--;
  27.             }
  28.         }
  29.         //两个栈当中 元素的个数是相同的
  30.         while (!stackP.isEmpty() && !stackQ.isEmpty()) {
  31.             if(stackP.peek() .equals(stackQ.peek())) {
  32.                 return stackP.peek();
  33.             }
  34.             stackP.pop();
  35.             stackQ.pop();
  36.         }
  37.         return null;
  38.     }

当然，这个写法的效率就比较低了，因为操作很频繁。

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

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

这个题就是我们之前的选择题的程序代码不是吗？你一定要理解之前的判断原理，才能够写出这个代码。

力扣：105. 从前序与中序遍历序列构造二叉树 - 力扣（Leetcode） 

  1. class TreeNode {
  2.     int val;
  3.     TreeNode left;
  4.     TreeNode right;
  5.     
  6.     TreeNode(int val) {
  7.         this.val = val;
  8.     }
  9. }
  10.  
  11. class Solution {
  12.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  13.         return buildTreeHelper(preorder, inorder, 0, 0, inorder.length - 1);
  14.     }
  15.     
  16.     private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
  17.         if (preStart > preorder.length - 1 || inStart > inEnd) {
  18.             return null;
  19.         }
  20.         
  21.         TreeNode root = new TreeNode(preorder[preStart]);
  22.         
  23.         int inIndex = 0;
  24.         for (int i = inStart; i <= inEnd; i++) {
  25.             if (inorder[i] == root.val) {
  26.                 inIndex = i;
  27.                 break;
  28.             }
  29.         }
  30.         
  31.         root.left = buildTreeHelper(preorder, inorder, preStart + 1, inStart, inIndex - 1);
  32.         root.right = buildTreeHelper(preorder, inorder, preStart + inIndex - inStart + 1, inIndex + 1, inEnd);
  33.         
  34.         return root;
  35.     }
  36. }

在buildTree函数中，我们调用辅助函数buildTreeHelper来构建二叉树。辅助函数接受先序遍历数组preorder、中序遍历数组inorder，以及先序遍历的起始位置preStart、中序遍历的起始位置inStart和结束位置inEnd作为参数。首先，我们检查基准情况，如果preStart大于先序遍历数组的最大索引值或inStart大于inEnd，则返回null，表示空树。否则，我们创建一个根节点，值为preorder[preStart]。接下来，我们在中序遍历数组inorder中找到根节点的索引inIndex，然后根据inIndex将中序遍历数组分为左子树和右子树。递归地构建左子树和右子树，并将它们分别作为根节点的左孩子和右孩子。最后，返回根节点。

这里面，preStart + inIndex - inStart + 1 或许需要作出一些解释：

我们首先需要明确一个点——我们现在在干什么？我们在创建右子树。

这里的右子树有什么？以图上的树为例：我们有以E作为根节点的J、K、G形成的右子树，有以F为根节点的 I 形成的右子树。

所以，preStart其实是我们用来确定此次根节点的指标。也就是说，此次的前序遍历是从preStart开始的，而前序遍历里面第一个节点就是根节点。我们最终需要得到的“ preStart + inIndex - inStart + 1 ” 就是在前序遍历里面的坐标。

接下来的“inIndex - inStart” 是中序遍历里面本次的根节点距离本次子树的中序遍历开头节点的相对距离（每调用一遍这个方法，都会生成新的Index）。

最后+1，代表坐标后挪一位，是我们中序遍历里面紧挨着中间节点的“左根右”里的右子树的根节点。

当然，如果实在不好理解，我们可以把“找中间根节点”提出去单独作为一个方法，这样就很好确认各节点的坐标了：

  1.     class Solution {
  2.  
  3.  
  4.         public int priIndex;
  5.  
  6.         public TreeNode buildTree(int[] preorder, int[] inorder) {
  7.  
  8.             return buildTreeChild(preorder,inorder,0,inorder.length-1);
  9.         }
  10.  
  11.         private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {
  12.  
  13.             //1. 没有左树 或者 没有右树了
  14.             if(inbegin > inend) {
  15.                 return null;
  16.             }
  17.             //2.创建根节点
  18.             TreeNode root = new TreeNode(preorder[priIndex]);
  19.  
  20.             //3.从中序遍历当中 找到根节点所在的下标
  21.             int rootIndex = findIndex(inorder,inbegin,inend,preorder[priIndex]);
  22.             if(rootIndex == -1) {
  23.                 return null;
  24.             }
  25.  
  26.             priIndex++;
  27.             //4. 创建左子树 和  右子树
  28.             root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
  29.  
  30.             root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
  31.  
  32.             return root;
  33.         }
  34.  
  35.         private int findIndex(int[] inorder,int inbegin,int inend,int key) {
  36.             for(int i = inbegin;i <= inend;i++) {
  37.                 if(inorder[i] == key) {
  38.                     return i;
  39.                 }
  40.             }
  41.             return -1;
  42.         }
  43.     }

注意: 我们最好把priIndex（ prestart） 定义为成员变量。

通过这个程序，可以根据先序遍历数组和中序遍历数组构造二叉树，并返回根节点。

 力扣的官方题解还给出了另一种奇特的办法——迭代，但是不是很好理解，你需要多看一会儿，优点是，它的时间复杂度很低（我建议你去看看力扣的官方的解析，比较多，我就不粘贴过来了，前面已经放了链接）：

  1. class Solution {
  2.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  3.         if (preorder == null || preorder.length == 0) {
  4.             return null;
  5.         }
  6.         TreeNode root = new TreeNode(preorder[0]);
  7.         Deque<TreeNode> stack = new LinkedList<TreeNode>();
  8.         stack.push(root);
  9.         int inorderIndex = 0;
  10.         for (int i = 1; i < preorder.length; i++) {
  11.             int preorderVal = preorder[i];
  12.             TreeNode node = stack.peek();
  13.             if (node.val != inorder[inorderIndex]) {
  14.                 node.left = new TreeNode(preorderVal);
  15.                 stack.push(node.left);
  16.             } else {
  17.                 while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
  18.                     node = stack.pop();
  19.                     inorderIndex++;
  20.                 }
  21.                 node.right = new TreeNode(preorderVal);
  22.                 stack.push(node.right);
  23.             }
  24.         }
  25.         return root;
  26.     }
  27. }

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

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

这题和刚刚的没有什么太大的区别，无非是前序遍历和后序遍历的不同。

力扣：106. 从中序与后序遍历序列构造二叉树 - 力扣（Leetcode）

  1. class TreeNode {
  2.     int val;
  3.     TreeNode left;
  4.     TreeNode right;
  5.     
  6.     TreeNode(int val) {
  7.         this.val = val;
  8.     }
  9. }
  10.  
  11. class Solution {
  12.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  13.         return buildTreeHelper(inorder, postorder, 0, inorder.length - 1, postorder.length - 1);
  14.     }
  15.     
  16.     private TreeNode buildTreeHelper(int[] inorder, int[] postorder, int inStart, int inEnd, int postEnd) {
  17.         if (inStart > inEnd || postEnd < 0) {
  18.             return null;
  19.         }
  20.         
  21.         TreeNode root = new TreeNode(postorder[postEnd]);
  22.         
  23.         int inIndex = 0;
  24.         for (int i = inStart; i <= inEnd; i++) {
  25.             if (inorder[i] == root.val) {
  26.                 inIndex = i;
  27.                 break;
  28.             }
  29.         }
  30.         
  31.         //注意：一定是先右后左
  32.         root.right = buildTreeHelper(inorder, postorder, inIndex + 1, inEnd, postEnd - 1);
  33.         root.left = buildTreeHelper(inorder, postorder, inStart, inIndex - 1, postEnd - (inEnd - inIndex) - 1);
  34.         
  35.         return root;
  36.     }
  37. }

在buildTree函数中，我们调用辅助函数buildTreeHelper来构建二叉树。辅助函数接受中序遍历数组inorder、后序遍历数组postorder，以及中序遍历的起始位置inStart和结束位置inEnd，以及后序遍历的结束位置postEnd作为参数。首先，我们检查基准情况，如果inStart大于inEnd或postEnd小于0，则返回null，表示空树。否则，我们创建一个根节点，值为postorder[postEnd]。接下来，我们在中序遍历数组inorder中找到根节点的索引inIndex，然后根据inIndex将中序遍历数组分为左子树和右子树。递归地构建右子树和左子树，并将它们分别作为根节点的右孩子和左孩子。最后，返回根节点。

这里就和前面反过来了，右树比较好确定，左树的话就比较难确定：

通过这个程序，就可以根据中序遍历数组和后序遍历数组构造二叉树，并返回根节点。

同样的，我们也可以改一下代码便于理解：

  1. class Solution {
  2.  
  3.  
  4.     public int postIndex ;
  5.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  6.  
  7.         postIndex = postorder.length-1;
  8.  
  9.         return buildTreeChild(postorder,inorder,0,inorder.length-1);
  10.     }
  11.  
  12.     private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend) {
  13.  
  14.         //1. 没有左树 或者 没有右树了
  15.         if(inbegin > inend) {
  16.             return null;
  17.         }
  18.         //2.创建根节点
  19.         TreeNode root = new TreeNode(postorder[postIndex]);
  20.  
  21.         //3.从中序遍历当中 找到根节点所在的下标
  22.         int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
  23.         if(rootIndex == -1) {
  24.             return null;
  25.         }
  26.  
  27.         postIndex--;
  28.         //4. 创建左子树 和  右子树
  29.  
  30.         root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
  31.  
  32.         root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
  33.  
  34.         return root;
  35.     }
  36.  
  37.     private int findIndex(int[] inorder,int inbegin,int inend,int key) {
  38.         for(int i = inbegin;i <= inend;i++) {
  39.             if(inorder[i] == key) {
  40.                 return i;
  41.             }
  42.         }
  43.         return -1;
  44.     }
  45. }

力扣的迭代写法：

  1. class Solution {
  2.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  3.         if (postorder == null || postorder.length == 0) {
  4.             return null;
  5.         }
  6.         TreeNode root = new TreeNode(postorder[postorder.length - 1]);
  7.         Deque<TreeNode> stack = new LinkedList<TreeNode>();
  8.         stack.push(root);
  9.         int inorderIndex = inorder.length - 1;
  10.         for (int i = postorder.length - 2; i >= 0; i--) {
  11.             int postorderVal = postorder[i];
  12.             TreeNode node = stack.peek();
  13.             if (node.val != inorder[inorderIndex]) {
  14.                 node.right = new TreeNode(postorderVal);
  15.                 stack.push(node.right);
  16.             } else {
  17.                 while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
  18.                     node = stack.pop();
  19.                     inorderIndex--;
  20.                 }
  21.                 node.left = new TreeNode(postorderVal);
  22.                 stack.push(node.left);
  23.             }
  24.         }
  25.         return root;
  26.     }
  27. }

11. 二叉树创建字符串

 给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

 力扣：606. 根据二叉树创建字符串 - 力扣（Leetcode）

  1. class TreeNode {
  2.     int val;
  3.     TreeNode left;
  4.     TreeNode right;
  5.     
  6.     TreeNode(int val) {
  7.         this.val = val;
  8.     }
  9. }
  10.  
  11. class Solution {
  12.     public String tree2str(TreeNode root) {
  13.         if (root == null) {
  14.             return "";
  15.         }
  16.         
  17.         StringBuilder sb = new StringBuilder();
  18.         tree2strHelper(root, sb);
  19.         return sb.toString();
  20.     }
  21.     
  22.     private void tree2strHelper(TreeNode root, StringBuilder sb) {
  23.         if (root == null) {
  24.             return;
  25.         }
  26.         //根节点前面没有括号
  27.         sb.append(root.val);
  28.         
  29.         if (root.left != null || root.right != null) {
  30.             sb.append("(");
  31.             tree2strHelper(root.left, sb);
  32.             sb.append(")");
  33.         }
  34.         
  35.         if (root.right != null) {
  36.             sb.append("(");
  37.             tree2strHelper(root.right, sb);
  38.             sb.append(")");
  39.         }
  40.     }
  41. }

在tree2str函数中，我们首先检查根节点是否为空，如果为空则返回空字符串。否则，我们创建一个StringBuilder对象sb用于构建结果字符串，并调用辅助函数tree2strHelper来进行递归遍历。辅助函数接受当前节点root和StringBuilder对象sb作为参数。首先，我们将当前节点的值添加到sb中。然后，我们检查当前节点的左子树和右子树是否存在。如果至少一个子树存在，我们在结果字符串中添加一个左括号"("，然后递归处理左子树，并在结果字符串中添加一个右括号")"。如果右子树存在，我们再次在结果字符串中添加一个左括号"("，然后递归处理右子树，并在结果字符串中添加一个右括号")"。通过这样的方式，我们可以按照前序遍历的顺序将二叉树转化为字符串。

或者分为：

1、左边不为空：右边为空和右边不为空；

2、左边为空：右边为空和右边不为空；

3、右边不为空；

4、右边为空。（因为反正最后（）都要省略掉）

  1.     public String tree2str(TreeNode root) {
  2.         StringBuilder stringBuilder  = new StringBuilder();
  3.         tree2strChild(root,stringBuilder);
  4.         return stringBuilder.toString();
  5.     }
  6.  
  7.     private void tree2strChild(TreeNode t,StringBuilder stringBuilder) {
  8.         if(t == null) {
  9.             return;
  10.         }
  11.         stringBuilder.append(t.val);
  12.         if(t.left != null) {
  13.             stringBuilder.append("(");
  14.             tree2strChild(t.left,stringBuilder);
  15.             stringBuilder.append(")");
  16.         }else {
  17.             if(t.right == null) {
  18.                 return;
  19.             }else{
  20.                 stringBuilder.append("()");
  21.             }
  22.         }
  23.         if(t.right != null) {
  24.             stringBuilder.append("(");
  25.             tree2strChild(t.right,stringBuilder);
  26.             stringBuilder.append(")");
  27.         }else {
  28.             return;
  29.         }
  30.     }

力扣给的官方题解更简洁，直接区分了两种情况：没有右子树的需要省略空括号的，可能没有左子树的不能省略空括号的大部分情况（我稍微拆开了了一点，方便看）：

  1. class Solution {
  2.     public String tree2str(TreeNode root) {
  3.         if (root == null) {
  4.             return "";
  5.         }
  6.         if (root.left == null && root.right == null) {
  7.             return Integer.toString(root.val);
  8.         }
  9.         if (root.right == null) {
  10.             return new StringBuffer().append(root.val)
  11.                                      .append("(")
  12.                                      .append(tree2str(root.left))
  13.                                      .append(")")
  14.                                      .toString();
  15.         }
  16.  
  17.         return new StringBuffer().append(root.val)
  18.                                  .append("(")
  19.                                  .append(tree2str(root.left))
  20.                                  .append(")(")
  21.                                  .append(tree2str(root.right))
  22.                                  .append(")")
  23.                                  .toString();
  24.         }
  25. }
  26.

这样，我们就可以将二叉树按照前序遍历的方式转化为字符串，并返回构造出的字符串。

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

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

力扣：144. 二叉树的前序遍历 - 力扣（Leetcode）

1、递归（我们写过了）

  1. import java.util.ArrayList;
  2. import java.util.List;
  3.  
  4. class TreeNode {
  5.     int val;
  6.     TreeNode left;
  7.     TreeNode right;
  8.     
  9.     TreeNode(int val) {
  10.         this.val = val;
  11.     }
  12. }
  13.  
  14. class Solution {
  15.     public List<Integer> preorderTraversal(TreeNode root) {
  16.         List<Integer> result = new ArrayList<>();
  17.         preorderTraversalHelper(root, result);
  18.         return result;
  19.     }
  20.     
  21.     private void preorderTraversalHelper(TreeNode root, List<Integer> result) {
  22.         if (root == null) {
  23.             return;
  24.         }
  25.         
  26.         result.add(root.val);
  27.         preorderTraversalHelper(root.left, result);
  28.         preorderTraversalHelper(root.right, result);
  29.     }
  30. }

2、迭代

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Stack;
  4.  
  5. class TreeNode {
  6.     int val;
  7.     TreeNode left;
  8.     TreeNode right;
  9.     
  10.     TreeNode(int val) {
  11.         this.val = val;
  12.     }
  13. }
  14.  
  15. class Solution {
  16.     public List<Integer> preorderTraversal(TreeNode root) {
  17.         List<Integer> result = new ArrayList<>();
  18.         if (root == null) {
  19.             return result;
  20.         }
  21.         
  22.         Stack<TreeNode> stack = new Stack<>();
  23.         stack.push(root);
  24.         
  25.         while (!stack.isEmpty()) {
  26.             TreeNode node = stack.pop();
  27.             result.add(node.val);
  28.             
  29.             if (node.right != null) {
  30.                 stack.push(node.right);
  31.             }
  32.             
  33.             if (node.left != null) {
  34.                 stack.push(node.left);
  35.             }
  36.         }
  37.         
  38.         return result;
  39.     }
  40. }

 注意，这里前序遍历是“根左右”，而先压入栈中的元素是最后出栈的，所以我们先把右子树压进去，再压左子树。

或者：

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Stack;
  4.  
  5. /**
  6.  * Definition for a binary tree node.
  7.  * public class TreeNode {
  8.  *     int val;
  9.  *     TreeNode left;
  10.  *     TreeNode right;
  11.  *     TreeNode() {}
  12.  *     TreeNode(int val) { this.val = val; }
  13.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  14.  *         this.val = val;
  15.  *         this.left = left;
  16.  *         this.right = right;
  17.  *     }
  18.  * }
  19.  */
  20. class Solution {
  21.     public List<Integer> preorderTraversal(TreeNode root) {
  22.         List<Integer> result = new ArrayList<>();
  23.         if (root == null) return result;
  24.  
  25.         Stack<TreeNode> stack = new Stack<>();
  26.         TreeNode cur = root;
  27.  
  28.         while (cur != null || !stack.isEmpty()) {
  29.             while (cur != null) {
  30.                 stack.push(cur);
  31.                 result.add(cur.val);
  32.                 cur = cur.left;
  33.             }
  34.  
  35.             TreeNode top = stack.pop();
  36.             cur = top.right;
  37.         }
  38.  
  39.         return result;
  40.     }
  41. }

如果只是简单的打印出来：

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

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

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

力扣：94. 二叉树的中序遍历 - 力扣（Leetcode）

1、递归

  1. import java.util.ArrayList;
  2. import java.util.List;
  3.  
  4. class TreeNode {
  5.     int val;
  6.     TreeNode left;
  7.     TreeNode right;
  8.     
  9.     TreeNode(int val) {
  10.         this.val = val;
  11.     }
  12. }
  13.  
  14. class Solution {
  15.     public List<Integer> inorderTraversal(TreeNode root) {
  16.         List<Integer> result = new ArrayList<>();
  17.         inorderTraversalHelper(root, result);
  18.         return result;
  19.     }
  20.     
  21.     private void inorderTraversalHelper(TreeNode root, List<Integer> result) {
  22.         if (root == null) {
  23.             return;
  24.         }
  25.         
  26.         inorderTraversalHelper(root.left, result);
  27.         result.add(root.val);
  28.         inorderTraversalHelper(root.right, result);
  29.     }
  30. }

2、迭代

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Stack;
  4.  
  5. class TreeNode {
  6.     int val;
  7.     TreeNode left;
  8.     TreeNode right;
  9.     
  10.     TreeNode(int val) {
  11.         this.val = val;
  12.     }
  13. }
  14.  
  15. class Solution {
  16.     public List<Integer> inorderTraversal(TreeNode root) {
  17.         List<Integer> result = new ArrayList<>();
  18.         if (root == null) {
  19.             return result;
  20.         }
  21.         
  22.         Stack<TreeNode> stack = new Stack<>();
  23.         TreeNode curr = root;
  24.         
  25.         while (curr != null || !stack.isEmpty()) {
  26.             while (curr != null) {
  27.                 stack.push(curr);
  28.                 curr = curr.left;
  29.             }
  30.             
  31.             curr = stack.pop();
  32.             result.add(curr.val);
  33.             curr = curr.right;
  34.         }
  35.         
  36.         return result;
  37.     }
  38. }

如果只是简单的打印出来：

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

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

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

力扣：145. 二叉树的后序遍历 - 力扣（Leetcode）

1、递归

  1. import java.util.ArrayList;
  2. import java.util.List;
  3.  
  4. class TreeNode {
  5.     int val;
  6.     TreeNode left;
  7.     TreeNode right;
  8.     
  9.     TreeNode(int val) {
  10.         this.val = val;
  11.     }
  12. }
  13.  
  14. class Solution {
  15.     public List<Integer> postorderTraversal(TreeNode root) {
  16.         List<Integer> result = new ArrayList<>();
  17.         postorderTraversalHelper(root, result);
  18.         return result;
  19.     }
  20.     
  21.     private void postorderTraversalHelper(TreeNode root, List<Integer> result) {
  22.         if (root == null) {
  23.             return;
  24.         }
  25.         
  26.         postorderTraversalHelper(root.left, result);
  27.         postorderTraversalHelper(root.right, result);
  28.         result.add(root.val);
  29.     }
  30. }

2、迭代

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Stack;
  4.  
  5. class TreeNode {
  6.     int val;
  7.     TreeNode left;
  8.     TreeNode right;
  9.     
  10.     TreeNode(int val) {
  11.         this.val = val;
  12.     }
  13. }
  14.  
  15. class Solution {
  16.     public List<Integer> postorderTraversal(TreeNode root) {
  17.         List<Integer> result = new ArrayList<>();
  18.         if (root == null) {
  19.             return result;
  20.         }
  21.         
  22.         Stack<TreeNode> stack = new Stack<>();
  23.         TreeNode curr = root;
  24.         TreeNode lastVisited = null;
  25.         
  26.         while (curr != null || !stack.isEmpty()) {
  27.             while (curr != null) {
  28.                 stack.push(curr);
  29.                 curr = curr.left;
  30.             }
  31.             
  32.             TreeNode peekNode = stack.peek();
  33.             //lastVisited 是作为一个标志值，代表该值已经被打印过！
  34.             if (peekNode.right == null || peekNode.right == lastVisited) {
  35.                 result.add(peekNode.val);
  36.                 lastVisited = stack.pop();
  37.             } else {
  38.                 curr = peekNode.right;
  39.             }
  40.         }
  41.         
  42.         return result;
  43.     }
  44. }

逐步压栈，直到找到最左边的元素，再去看看它有没有右子树。没有右子树的话，就相当于它是一个叶子节点，可以压到结果栈里面了。有的话就代表它不是叶子节点，而是一个有右子树的根节点，因为后序遍历是先右边再为根，所以再去定位右边子树为新的节点，去找它的最左边。
因为压栈就等于已经保存了一个逐次调用的顺序了，所以我们可以逐次弹出每一层的主节点，在依次去每次判断每个节点的右子树的情况。 

注意：if (peekNode.right == null || peekNode.right == lastVisited) 的重要性！！！

一定要有这个条件，否则会陷入死循环！因为 lastVisited 作为表示已经被打印过的值，需要避免再打印一次，并且令 lastVisited 等于新的弹出的元素。

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

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

  

闽ICP备14008679号