二叉树

树

初识树

树是一种非线性的分层数据结构，由节点（或称作“结点”）组成，具有明确的层次关系和父子关系。

详细定义：树是由n（n≥0）个节点组成的有限集。当n=0时称为空树；在非空树中，有一个特定的节点被称为“根”，并且除根节点外的其余节点被分成m（m>0）个互不相交的集合，每个集合本身又是一棵树，并称之为根的子树。

之所以叫树，就是因为这个数据结构像一棵倒挂的树，根在上，叶子在下。判断一棵树有以下注意点：

• 子树是不相交的，如图，以A为根节点的树有三个子树，分别以 B、C、D为根节点
• 除了根节点外，每个结点有且仅有一个父结点
• 一棵含有n个结点的树有 n - 1 条边
• 树的结构没有回路，如果有箭头，就先将箭头忽略，存在回路，就一定不是树
• 树是递归定义的

下图三种结构就不是树：

---

有关树的概念

概念	解释	以上图举例
结点的度	一个结点含有子树的个数	E的度为2；F的度为3
树的度	一棵树中所有结点度的最大值	树的度为A的度，为6
叶子结点(终端结点)	度为0的结点	B、C、H等
父结点(双亲结点)	直接上层结点	I的父结点为E；L的父结点为F
子结点(孩子结点)	直接下层结点	E的子结点有I、J
根结点	没有父结点的结点	A为根节点
结点的层次	从根开始，根结点为第1层，根结点的子结点为第二层，以此类推	A所在第1层，P所在层为第4层
树的高度(深度)	树中结点的最大层次，有时候将深度和高度区分，即高度是最大深度	高度为4
分支结点(非终端结点)	度不为0的结点	D、E、F等
兄弟结点	具有相同父结点的结点互称为兄弟结点	P、Q互为兄弟结点
堂兄弟结点	父结点在同一层的结点互称为堂兄弟结点	H、I互为堂兄弟结点
结点的祖先	从根到该结点所经分支上的所有结点	除了A，所有结点都有祖先A
子孙	以某结点为根的子树中任一结点都称为该结点的子孙	除本身，所有结点都是A的子孙

表中加粗的概念为重点掌握概念。

---

树的表示

树可以采用多种方法进行表示，主要包括双亲表示法、孩子表示法和孩子兄弟表示法等。具体如下：

1. 双亲表示法：这种方法通过一组连续空间来存储树的结点，并在每个结点中附加一个指示器，用于指示其双亲结点在数组中的位置。这种结构使得每个结点都知道其双亲结点的位置，从而方便地查找到结点的双亲。不过，这种表示法的缺点是查找结点的孩子结点比较困难，需要遍历整个结构。
2. 孩子表示法：鉴于树中的每个结点可能有多个孩子，这种方法使用多重链表表示。具体有两种方案：一种是设置固定数量的引用域，存储所有孩子结点的地址；另一种是按需为每个结点分配引用域，即每个结点引用域的个数等于该结点的度。这种表示法便于查找结点的孩子结点，但在查找父结点时不如双亲表示法便捷。
3. 孩子兄弟表示法：这种方法将普通树转化为二叉树进行处理。在这种表示法中，每个结点除了数据域外，还包含两个引用域，分别指向该结点的第一个孩子和下一个兄弟。这种方法适用于需要频繁查找结点的孩子和兄弟结点的情况，并且能够有效减少存储空间的浪费。

以了解为主，下图为孩子兄弟表示法的示意图：

---

树的应用

树的结构在计算机科学和各个领域中有着广泛的应用，主要包括文件系统、数据库索引、解析器、网络路由和数据压缩等。

文件管理：

感兴趣的可以自行查阅！

---

二叉树

二叉树的概念

二叉树是一种特殊的数据结构，它是由节点组成的树形结构。每个节点最多有两个子节点，通常称为左子节点和右子节点。

二叉树的特点是每个节点最多有两个子节点（不存在度数大于2的结点），且子节点有左右之分（左右孩子不等价，不能随意交换），没有结点的空树和只有根节点的树都算二叉树。

---

【特殊二叉树】

满二叉树，每层的结点数都达到最大值得二叉树成为满二叉树。

如果一棵二叉树得层数为 k，且结点总数是 2^k - 1，那么这棵二叉树就是满二叉树。

完全二叉树，它的特点是除了最后一层外，其他层的结点都被元素填满，且最后一层的结点都靠左排列。也就是说，如果一个二叉树的高度为h，那么它的第 i 层（从1开始计数）最多有2^(h-i)个结点。满二叉树是一种特殊的完全二叉树

判断下图中二叉树是否是完全二叉树：

不是完全二叉树，因为最后一层的结点没有靠左排列，所以不满足完全二叉树。

---

二叉树的性质

1.一棵结点数为 n 的树有 n-1 条边（二叉树当然也满足，写在这里只是为了强调）
2. 若规定根结点的层数为1，则一棵非空二叉树的第 i 层上最多有2^(i-1)个结点。

3. 若规定根节点的层数为1，则深度为 h 的二叉树的最大节点数是2^h - 1。

4. 对任何一棵二叉树，如果度为 0 的叶节点的个数为 n0，度为 2 的分支结点个数为 n2，则有n0 = n2 + 1。

5. 具有 n 个结点的完全二叉树的深度 h 为log2(n + 1) ，结果向上取整。

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

• 若 i > 0，父结点的编号：(i - 1) / 2;若 i = 0，即 i 为根结点编号，无父结点
• 若 2*i+1 < n，左孩子结点编号：2 * i + 1，否则无左孩子
• 若 2*i+2 < n，右孩子结点编号：2 * i + 2，否则无右孩子

【注意】

• 性质1、2、3、4是针对所有二叉树的；性质5、6是针对完全二叉树的

• 给出性质4的证明：

  假设：

  任意一棵结点数为 n 的二叉树，度为0的结点数为 n0，度为1的结点数为 n1，度为2的结点数为 n2

  已知：

  度为0的结点为二叉树提供0条边，度为1的结点为二叉树提供1条边，度为2的结点为二叉树提供2条边

  可证：

  二叉树的边数为 n-1（根据性质1）

  n = n0 + n1 + n2

  n - 1 = n0×0 + n1×1 + n2×2

  化简：

  n0 + n1 + n2 = n1 + n2 + n2 + 1

  结论：

  n0 = n2 + 1

---

二叉树的性质这一部分经常考察选择题，我们尝试利用性质解决几道：

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

   A. n B. n+1 C. n-1 D. n/2

2. 一个具有767个结点的完全二叉树，其叶子结点个数为（）

   A. 383 B. 384 C. 385 D. 386

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

   A. 11 B. 10 C. 8 D. 12

---

1. 根据完全二叉树的特点，可得：完全二叉树度为1的结点数（n1）只可能是1或0

   假设n1 = 0，则 n1 + n2 + n0 = 2n，化简得：0 + n0 - 1 + n0 = 2n，结果为：2*n0 = 2n - 1，n0不为整数，所以假设不成立

   假设n1 = 1，则 n1 + n2 + n0 = 2n，化简得：1 + n0 - 1 + n0 = 2n，结果为：2*n0 = 2n，故n0 = n ，A正确

2. 同样的方法，假设n1 = 0，0 + n0 - 1 + n0 = 767，得n0 = 384；再试试n1 = 1，有 1 + n0 - 1 + n0 = 767，n0解得不为整数。综上，选择B

3. 利用性质5： log2(531 + 1) = h，h介于9~10，向上取整为10，选择B

答案：A B B

---

二叉树的存储

二叉树的存储分为顺序存储和链式存储：

1. 顺序存储：将二叉树的所有结点按照一定顺序存储在一维数组中。通常有两种顺序存储方式：一种是按照层次顺序存储，另一种是按照先序、中序或后序遍历的顺序存储。顺序存储的优点是节省空间，缺点是访问结点的操作比较复杂，一般不采用这种方式。后面的堆会用到顺序存储。

2. 链式存储：每个节点包含一个数据元素和两个引用，分别指向该结点的左子结点和右子结点。链式存储的优点是访问结点的操作比较简单，缺点是占用的空间较大。常见的表示形式有三叉和二叉表示方法：

   //二叉表示：
   class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}
   }//三叉表示：
   class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode parent;public TreeNode(int val) {this.val = val;}
   }
   

   我们使用最多的就是链式存储的二叉表示，之后所有的题目都是以这种形式表示。

---

二叉树的遍历

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

二叉树的遍历分为 广度优先遍历 和 深度优先遍历：

深度优先遍历分为：前序遍历、中序遍历、后序遍历（前、中、后表示的是根节点的访问的时机）

广度优先遍历 对应：层序遍历

---

在前序遍历中，首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。在中序遍历中，首先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。在后序遍历中，首先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。

如上二叉树，以后序遍历为例，遵循左 右 根的规则：

先到A，A为根，不访问A，先访问A的左子树到达B，B为新根，不访问B，先访问B的左子树到达D，D为新根，不访问D，先访问D的左子树到达H，H为新根，先访问H的左子树，为空，那就返回到H，仍然不访问H，刚访问完H的左子树，继续访问H的右子树到达K，K为新根，访问K的左为空，返回访问K的右也为空，此时访问K，可以选择打印K，然后返回到H，H的左右都访问完毕，访问H，打印H……以此类推，访问完树的所有结点并打印，打印结果就是后序遍历的结果。

对上图进行深度优先遍历的结果：

前序遍历：A B D H K E C F I G J

中序遍历：H K D B E A I F C G J

后序遍历：K H D E B I F J G C A

我们发现，前中后序遍历的路线是一致的，只不过访问结点的时机不同。

---

既然给出一棵树，我们能写出前中后序遍历，那么给出前中后序遍历的序列，我们能否构建出一棵唯一的二叉树呢？

是可以的，不难推测，仅一种遍历序列无法确定，两种遍历序列就可以，分析前中后序的特点：

• 前序序列：第一个一定是根结点
• 中序序列：根据根结点，就能确定其左子树和右子树的结点
• 后序序列：最后一个一定是根结点

给出结论：前序序列和中序序列、后序序列和中序序列 可以确定唯一一棵二叉树，而前序序列和后序序列是不可以的，它们都只能确定根结点，所以，双遍历构建二叉树必须包括中序遍历。

现有前序序列：[3, 9, 20, 15, 7]，中序序列：[9, 3, 15, 20, 7]，构建该二叉树：

• 构建的顺序就是前序序列顺序，左右子树是 先构建左 再构建右

现有后序序列：[9, 15, 7, 20, 3]，中序序列：[9, 3, 15, 20, 7]，构建该二叉树：

• 构建的顺序就是后序序列的顺序，左右子树是 先构建右 再构建左

后面练习部分就有双遍历构建二叉树的题目，思路也是从前序（后序）中依次从左向右（从右向左）取一个数据，在中序序列中找该数据的位置，据此划分左树和右树的区间

---

层序遍历：从根结点开始，逐层遍历二叉树，每层从左到右访问结点。

对于上图，层序遍历的结果为：A B C D E F G H I J K

遍历操作的代码实现在下一模块。

---

二叉树的操作(代码实现)

遍历

遍历：

这一部分主要介绍二叉树四种遍历的代码实现，具体包括：

• 前序、中序、后序遍历的递归以及非递归实现（将序列打印出来）
• 层序遍历以及判断一棵树是否是完全二叉树

【前中后序递归】

二叉树是递归定义的，对二叉树的深度优先遍历采用递归方式实现的代码是比较简单的：

    // 前序遍历public void preOrder(TreeNode root) {if(root == null) {return;}System.out.print(root.val + " ");preOrder(root.left);preOrder(root.right);}// 中序遍历void inOrder(TreeNode root) {if(root == null) {return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}// 后序遍历void postOrder(TreeNode root) {if(root == null) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");}

• 打印时机就是访问结点的时机，三种遍历语句做出简单的调换即可！

【前中后序非递归】

非递归实现要用到 栈，来保存一些结点防止遍历深处时无法返回。

• 前序遍历：

  1. 首先检查根节点是否为空，如果为空则直接返回，因为空树没有节点需要遍历。
  2. 创建一个栈来存储待访问的节点。
  3. 初始化当前节点为根节点。
  4. 当当前节点不为空或者栈不为空时，执行以下操作： a. 将当前节点压入栈中，并打印当前节点的值。 b. 将当前节点更新为其左子节点。
  5. 如果当前节点为空，说明已经到达了最左边的叶子节点，此时从栈中弹出一个节点作为下一个要访问的节点。
  6. 将当前节点更新为弹出节点的右子节点。
  7. 重复步骤4和6，直到当前节点为空且栈为空。

      public void preOrderNor(TreeNode root) {if(root == null) return;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);System.out.print(cur.val + " ");cur = cur.left;}TreeNode top = stack.pop();cur = top.right;}}
  

• 中序遍历：

  1. 首先检查根节点是否为空，如果为空则直接返回，因为空树没有节点需要遍历。
  2. 创建一个栈来存储待访问的节点。
  3. 初始化当前节点为根节点。
  4. 当当前节点不为空或者栈不为空时，执行以下操作： a. 将当前节点压入栈中，并将当前节点更新为其左子节点。 b. 如果当前节点为空，说明已经到达了最左边的叶子节点，此时从栈中弹出一个节点作为下一个要访问的节点，并打印该节点的值。 c. 将当前节点更新为弹出节点的右子节点。
  5. 重复步骤4和6，直到当前节点为空且栈为空。

      public void inOrderNor(TreeNode root) {if(root == null) return;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}TreeNode top = stack.pop();System.out.print(top.val + " ");cur = top.right;}}
  

• 后序遍历：

  1. 首先检查根节点是否为空，如果为空则直接返回，因为空树没有节点需要遍历。
  2. 创建一个栈来存储待访问的节点。
  3. 初始化当前节点为根节点，以及一个辅助变量prev用于记录上一次访问的节点。
  4. 当当前节点不为空或者栈不为空时，执行以下操作： a. 将当前节点压入栈中，并将当前节点更新为其左子节点。 b. 如果当前节点为空，说明已经到达了最左边的叶子节点，此时从栈顶取出一个节点作为下一个要访问的节点。 c. 如果该节点没有右子节点或者其右子节点已经被访问过（即右子节点是prev），则打印该节点的值，并将其从栈中弹出，同时更新prev为当前节点。 d. 否则，将当前节点更新为栈顶节点的右子节点。
  5. 重复步骤4和6，直到当前节点为空且栈为空。

      public void postOrderNor(TreeNode root) {if(root == null) return;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}TreeNode top = stack.peek();if (top.right == null || top.right == prev) {System.out.print(top.val + " ");stack.pop();prev = top;} else {cur = top.right;}}}
  

• 三种非递归遍历都包含到不断向左遍历直到为空的过程，对于前序遍历，不断向左的过程就可以打印；对于中序遍历，需要走到最左边(为空)，即左边遍历完，才能根据栈的记录返回并打印，然后遍历右边；对于后序遍历，不断走到最左边(为空)，返回到上一层，需要判断此时右边是否有结点，没有，则直接打印并弹出；有，就需要先遍历右边，为了防止发生死循环（即打印过的结点不断重复打印），设置一个prev，在每次打印后更新它的值。当右边不再有结点或访问过时，才可以打印。

---

【层序遍历】

层序遍历需要用到 队列：

1. 首先检查根节点是否为空，如果为空则直接返回，因为空树没有节点可以遍历。
2. 创建一个队列（Queue），并将根节点加入队列。
3. 当队列不为空时，执行以下操作： a. 从队列中取出一个节点（队首元素）。 b. 打印该节点的值。 c. 如果该节点有左子节点，将左子节点加入队列。 d. 如果该节点有右子节点，将右子节点加入队列。（上层结点带出下层结点）
4. 重复步骤3，直到队列为空。

    void levelOrder(TreeNode root) {if(root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()) {TreeNode cur = queue.poll();System.out.print(cur.val + " ");if(cur.left != null) {queue.offer(cur.left);}if(cur.right != null) {queue.offer(cur.right);}}}

---

【判断一棵树是否是完全二叉树】

判断一棵树是否是完全二叉树用到了层序遍历的思路：

1. 首先检查根节点是否为空，如果为空则直接返回true，因为空树可以被认为是完全二叉树。
2. 创建一个队列（Queue），并将根节点加入队列。
3. 当队列不为空时，执行以下操作： a. 从队列中取出一个节点（队首元素）。 b. 如果该节点为null，说明已经到达了最后一个节点或者遇到了一个空节点，跳出循环。 c. 将该节点的左子节点和右子节点分别加入队列（即使为null，也加入队列）。
4. 继续遍历队列，直到遇到第一个null节点为止。
5. 遍历队列。
6. 如果在遍历过程中发现有非null节点，说明不是完全二叉树，返回 false。
7. 如果遍历完队列后没有发现非null节点，说明是完全二叉树，返回 true。

    boolean isCompleteTree(TreeNode root) {if(root == null) {return true;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()) {TreeNode cur = queue.poll();if(cur == null) {break;}queue.offer(cur.left);queue.offer(cur.right);}while(!queue.isEmpty()) {if(queue.poll() != null) {return false;}}return true;}

---

结点数

结点数：

这一部分主要介绍的内容具体如下：

• 求一棵二叉树的结点数
• 求一棵二叉树的叶子结点数
• 求二叉树第 K 层的结点数

【结点数】

具体步骤如下：

1. 首先检查根节点是否为空，如果为空则返回0，因为空树没有节点。
2. 如果根节点不为空，则递归地计算左子树和右子树的节点数量。
3. 将左子树和右子树的节点数量相加，再加上根节点本身（1），得到整个树的节点数量。
4. 返回计算出的节点数量。

    int size2(TreeNode root) {return root == null ? 0 : size2(root.left) + size2(root.right) + 1;}

• 用到了分治思想，即求整个二叉树的结点数，就是左子树的结点数加上右子树的结点数再加上本身

---

【叶子结点数】

要把握叶子结点的特点：左右子树都为空

具体思路：

1. 首先检查根节点是否为空，如果为空，则返回0，因为空树没有叶子节点。
2. 如果根节点不为空，接着检查它是否是叶子节点，即它的左右子节点都为空。如果是叶子节点，则返回1，因为叶子节点本身就是一个叶子节点。
3. 如果根节点不是叶子节点，那么递归地计算它的左子树和右子树的叶子节点数量，然后将这两个数量相加，得到整个树的叶子节点数量。
4. 最后返回计算出的叶子节点数量。

int getLeafNodeCount2(TreeNode root) {if(root == null) {return 0;}if(root.left == null && root.right == null) {return 1;}return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
}

• 这里采用了分治子问题的思路，我们也可以采用遍历思路：

    public static int leafSize = 0;void getLeafNodeCount1(TreeNode root) {if(root == null) {return;}if(root.left == null && root.right == null) {leafSize++;}getLeafNodeCount1(root.left);getLeafNodeCount1(root.right);}

• 遍历思路需要一个成员变量来全局地递增记录叶子节点的数量，而不能将计数器作为参数参与递归（形参的改变不影响实参）

---

【第K层结点数】

思路：

1. 首先检查根节点是否为空，如果为空，则返回0，因为空树没有节点。
2. 如果k等于1，说明我们要计算的是第一层（根节点所在的层），那么直接返回1，因为只有根节点这一个节点。
3. 如果k大于1，我们需要递归地计算左子树和右子树在第k-1层的节点数量，然后将这两个数量相加，得到整个树在第k层的节点数量。
4. 最后返回计算出的第k层的节点数量。

    int getKLevelNodeCount(TreeNode root, int k) {if(root == null) {return 0;}if(k == 1) {return 1;}return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);}

---

二叉树高度

二叉树的高度：

介绍求一棵二叉树的高度问题

按照分治思想，二叉树的高度等于根结点的左子树和右子树的较高高度 + 1，而根结点的左子树的高度等于它的左子树和右子树的较高高度 + 1，依次递归。

具体思路：

1. 首先检查根节点是否为空，如果为空，则返回0，因为空树的高度为0。
2. 如果根节点不为空，递归地计算左子树和右子树的高度。
3. 比较左子树和右子树的高度，取较大值加1作为当前树的高度。这是因为树的高度定义为从根节点到最远叶子节点的最长路径上的节点数，而这条路径必然经过高度较高的子树。
4. 最后返回计算出的树的高度。

    int getHeight(TreeNode root) {if(root == null) {return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}

---

查找

查找：

即查找具有特定值的节点

具体思路：

1. 首先检查根节点是否为空，如果为空，则返回null，因为空树中没有节点。
2. 如果根节点的值等于要查找的值val，那么返回根节点，因为我们找到了目标节点。
3. 如果根节点的值不等于val，我们需要继续在左子树和右子树中查找。首先递归地在左子树中查找，将结果存储在变量ret中。
4. 如果ret不为null，说明在左子树中找到了目标节点，直接返回ret。
5. 如果ret为null，说明在左子树中没有找到目标节点，接着递归地在右子树中查找，同样将结果存储在ret中。
6. 如果ret不为null，说明在右子树中找到了目标节点，直接返回ret。
7. 如果ret仍然为null，说明在整个树中都没有找到目标节点，返回null。

    TreeNode find(TreeNode root, char val) {if(root == null) {return null;}if(root.val == val) {return root;}TreeNode ret = find(root.left, val);if(ret != null) {return ret;}ret = find(root.right, val);if(ret != null) {return ret;}return null;}

---

二叉树的相关练习

每道题目的链接都在题目的结尾，建议自己先尝试一下。

对称二叉树

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

class Solution {public boolean isSymmetric(TreeNode root) {//补充代码}
}

【思路】

如上图，是一棵对称二叉树。观察：如果一棵二叉树是对称二叉树，需要满足根结点的左子树和右子树对称，那么左右子树对称得满足什么？ 接着观察：1. 满足左右子树的值相等（2 == 2） 2. 必须满足左树的左子树和右树的右子树的值相等（3 == 3），左树的右子树与右树的左子树相等（4 == 4）。条件2推广一下，其实是左树的左子树和右树的右子树对称，左树的右子树与右树的左子树对称，如此大问题就化为一个个小问题了，递归就可以解决这一问题。

前面的分析是在结构一致的情况下，在编写代码的时候不要忽略结构不同导致的不对称的情况，这是讨论数值是否相等的前提，在示例代码中都会体现（结构和数值的判断）

class Solution {public boolean isSymmetric(TreeNode root) {if(root == null) {return true;}return _isSymmetric(root.left, root.right);}public boolean _isSymmetric(TreeNode leftTree, TreeNode rightTree) {if(leftTree == null && rightTree != null || leftTree != null && rightTree == null) {return false;}if(leftTree == null && rightTree == null) {return true;}if(leftTree.val != rightTree.val) {return false;}return _isSymmetric(leftTree.left, rightTree.right) && _isSymmetric(leftTree.right, rightTree.left);}
}

• 原题目仅给出一个参数的主方法，我们分析得到递归需要两棵树，即两个参数，所以我们分装了一个子方法_isSymmetric

• 子方法的三个if：1. 判断树的根结点是否一个为空一个非空 2. 判断两个根是否全空 3. 判断两个根结点的值是否相等

  • 前两个if是处理结构问题，判断结构是否相等；最后一个if是处理数据问题，判断结构相等的情况下，数据是否相等

  • 前两个判断结构的if语句必须在最后一个判断数值的if语句前，否则会出现NullPointerException，而前两个的顺序可以调换

原题链接：101. 对称二叉树 - 力扣（LeetCode）

---

平衡二叉树

给定一个二叉树，判断它是否是平衡二叉树

平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。

class Solution {public boolean isBalanced(TreeNode root) {//补充代码}
}

【思路】

我们必须理解平衡二叉树的概念，先观察上图是否是一棵平衡二叉树？不是，因为根结点的左右子树的深度差超过了1，这提醒我们在判断一棵树是否为平衡二叉树时，不能单纯地看这棵树规不规整，乱不乱，而是要根据概念观察是否满足所有节点的左右子树的深度相差不超过 1

这道题目涉及到了深度，很容易想到求二叉树的深度，只要求出左右子树的深度再相减取绝对值，就能判断出该树是否是平衡二叉树，当然只判断根结点是不行的，必须将所有结点判断到。

我们很容易写下如下代码：

class Solution {public boolean isBalanced(TreeNode root) {if(root == null) {return true;}int l = maxDepth(root.left);int r = maxDepth(root.right);return Math.abs(l - r) <= 1 && isBalanced(root.left) && isBalanced(root.right);}public int maxDepth(TreeNode root) {if(root == null) {return 0;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;}
}

• 上面代码的时间复杂度为O(N^2)，其实还有优化的余地，看下图的树：

进入方法isBalanced，先求以B为根的树的高度，进入方法maxDepth，开始递归的过程，如上图，求得D的左右子树的高度分别为2和0，此时D结点得左右子树高度差已经大于1了，实际上已经可以得出结论了，但由于代码设计，我们不得不继续求A的右子树的高度，然后再分别以D、C为根结点递归地求它们的左右子树的高度，依次类推，我们实际上做了非常多的重复工作。

基于上图的提示，我们可以在求得每个结点的左右高度后直接判断左右高度是否大于1，如果是直接返回一个-1，用来标识此时树已经不是平衡二叉树了，再加上一些if判断，来避免重复工作以达到优化的效果。

class Solution {public int _isBalanced(TreeNode root) {if(root == null) {return 0;}int left = _isBalanced(root.left);if(left == -1) {return -1;}int right = _isBalanced(root.right);if(right == -1) {return -1;}if(Math.abs(right - left) > 1) {return -1;}return left > right ? left + 1 : right + 1;}public boolean isBalanced(TreeNode root) {return _isBalanced(root) != -1;}
}

原题链接：110. 平衡二叉树 - 力扣（LeetCode）

---

二叉树的构建及遍历

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

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextLine()) {//填写代码}}
}

【思路】

这道题目跟以前的不太一样，以前的题目大部分都是给出一个方法，我们实现该方法即可，这种类型称为 “接口型”；现在我们要解决的问题不仅仅是一个方法，题目仅给出一个字符串，我们要根据前序字符串构建二叉树，并遍历打印中序序列，根据打印结果判断题目对错，这样的类型称为 “IO型”，下面我们就来解决这道IO型题目：

1. 创建树结点内部类
2. 接收字符串并实现构建方法，该方法接收一个字符串，返回构建好的树的根结点
3. 实现中序遍历打印的方法
4. 主函数依次调用两个方法

以上分析不难发现，第1、3、4步比较简单，关键是第二步构造二叉树，比较陌生，但思路也比较简单，遍历字符串，先构建根结点，再递归的构建左树和右树即可，易错点在遍历字符串，肯定需要一个int类型"指针"指示当前遍历到的位置，如果将它作为方法参数，是不可以的，因为形参的改变不影响实参，也就是说，递归过程中方法改变的不是同一个变量，所以我们决定在类中新增一个成员变量，这样每次改变的就都是同一个变量了。

这道题目想明白其实是比较简单的，主要弄清楚这道IO型题目让我们做什么以及解决前序遍历字符串构建二叉树。

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {//结点内部类static class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}}public static int index = 0;//新增成员变量//构建树public static TreeNode createTree(String s) {if(s.charAt(index) == '#') {index++;return null;}TreeNode tree = new TreeNode(s.charAt(index));index++;tree.left = createTree(s);tree.right = createTree(s);return tree;}//中序遍历public static void inOrder(TreeNode root) {if(root == null) {return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) {index = 0;String s = in.nextLine();TreeNode tree = createTree(s);inOrder(tree);}}
}

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

---

前序和中序构造二叉树

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

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {//补充代码}
}

【思路】

1. 首先，我们需要了解前序遍历和中序遍历的特点。前序遍历的顺序是根节点->左子树->右子树，而中序遍历的顺序是左子树->根节点->右子树。
2. 根据前序遍历和中序遍历的结果，我们可以确定根节点的位置。在前序遍历结果中，第一个元素就是根节点的值；在中序遍历结果中，找到该节点，该根节点将序列分为两部分，左边是左子树的节点，右边是右子树的节点。
3. 递归地构建左子树和右子树。对于左子树，我们使用前序遍历的左子树部分和中序遍历的左子树部分；对于右子树，我们使用前序遍历的右子树部分和中序遍历的右子树部分。

主要涉及到区间的划分，从左遍历前序序列，每遍历完一个，就构造出一个结点。起初先拿到根结点，在中序遍历中寻找这个根结点，找到后，该位置左边都是根结点的左树上的结点（左区间），右树都是根结点的右树上的结点（右区间）

class Solution {private int index = 0;//指示前序序列中的位置//l是区间的左边界，r是区间的右边界public TreeNode _buildTree(int[] prev, int[] in, int l, int r) {//区间不存在if(l > r) {return null;}//前序序列取值int val = prev[index++];//构建该结点TreeNode root = new TreeNode(val);int i = 0;//在中序序列中寻找for(i = l; i <= r; i++) {if(in[i] == val) {break;}}//根据区间，递归地先构建左树，再构建右树root.left = _buildTree(prev, in, l, i - 1);root.right = _buildTree(prev, in, i + 1, r);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {index = 0;return _buildTree(preorder, inorder, 0, inorder.length - 1);}
}

原题链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

相似练习：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

---

最近的公共祖先

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

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

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//补充代码}
}

【思路】

如果两个结点中有一个是根结点，那么最近公共祖先就是根结点，如3和2的最近公共祖先就是3；

如果两个结点分别分布在根结点的左子树和右子树中，即不同侧，那么最近公共结点就是根结点，如2和8的最近公共祖先就是3

如果两个结点在根结点3的同侧呢？

• 如4和6，它们的最近公共祖先就是5
• 如2和4，它们的最近公共祖先就是2

同侧的两种情况可以转化为前两种大情况，像4和6，其实是分布在以5为根结点的树的两侧，转化为第二种大情况；2和4，其实是在以2为根结点的树中的，2就是根结点，转化为第一种大情况

第一种大情况较为简单，直接判断两个结点是否是当前树的根结点即可；第二种情况就需要递归地分别去左右树中寻找结点了

以下代码只是上思路的呈现，链接中有更加丰富多样的题解！

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) {return null;}if(root == p || root == q) {return root;}TreeNode findLeft = lowestCommonAncestor(root.left, p, q);TreeNode findRight = lowestCommonAncestor(root.right, p, q);if(findLeft != null && findRight != null) {return root;}else if(findLeft != null) {return findLeft;}else {return findRight;}}
}

原题链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）

---

二叉树构建字符串

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

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

class Solution {public String tree2str(TreeNode root) {//补充代码}
}

原题示例截图如下：（若观察不便可以点击底部链接查看）

【思路】

前提：前序遍历

拼接过程：

观察示例一，1 是根结点，直接拼接1，然后看左子树不为空拼接(，接着拼接2，再看 2 的左边 4 不为空，拼接(，再拼接4，4 的左边为空，右边也为空，返回，此时 2 的左边完成，拼接)，接着去 2 的右，左右均为空，返回到 1 ，1的左边完成，拼接)，再去 1 的右，不为空，拼接(，再拼接3，3 的左右均为空，返回到 1，1的右边完成，拼接)。

观察示例二，1 是根结点，直接拼接1，到左边 2 不为空，拼接(，然后拼接2，去 2 的左边，为空，但由于 2 的右边不为空，拼接()，此时去 2 的右边，不为空拼接(，再拼接4，4 的左右为空，一直返回到 2 ，2 的右完成，拼接)，返回到 1 ，1 的左边完成，拼接)，去1 的右，不为空，拼接(，再拼接3，3 的左右都为空，返回到 1， 1 的右边完成，拼接)

发现：

• 对于(，根结点不拼接，只有开始递归且目标不为空，才在递归前拼接，然后走到不为空目标结点，拼接结点数值，
• 当前结点左右均为空，不做任何事情，返回
• 当前结点的左边为空，但右边不为空，就得拼接()，然后去不为空的右边
• 结点从不为空的结点返回，拼接)

class Solution {public String tree2str(TreeNode root) {if(root == null) {return null;}StringBuilder stringBuilder = new StringBuilder();_tree2str(root, stringBuilder);return stringBuilder.toString();}public void _tree2str(TreeNode t, StringBuilder stringBuilder) {if(t == null) {return;}//拼接结点数据stringBuilder.append(t.val);if(t.left != null) {//不空，先拼接"("stringBuilder.append("(");//去左边_tree2str(t.left, stringBuilder);//从不为空的左边返回了，拼接")"stringBuilder.append(")");}else {//当前结点左右都为空，返回if(t.right == null) {return;}else {//当前结点左边空，但右边不空，拼接"()"stringBuilder.append("()");}}//左边完成，右边if(t.right != null) {//不空，先拼接"("stringBuilder.append("(");//去右边_tree2str(t.right, stringBuilder);//从不为空的右边返回了，拼接")"stringBuilder.append(")");}else {//右边为空，返回return;}}
}

原题链接：606. 根据二叉树创建字符串 - 力扣（LeetCode）

---

完