目录
1. 树形结构 (了解)
树是一种非线性的数据结构，它是由n（n>=0）个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树具有以下特点：
- 有一个特殊的节点，叫做根节点，根节点没有前驱节点。
- 出了根节点，其他的节点会被分成 M(M > 0) 个集合,每一个集合又是一颗与树类似的子树。每颗子树有且只有一个前驱，可以有 0 个或者多个后继。
- 树是递归定义的。
如图所示，下面就是一颗树：
注意：子树和子树之间不能有交集，否则就不是树形结构。
要点总结：
1. 一棵树 N 个节点，有 N - 1 条边。
2. 子树之间不能相交
3. 每一个节点只能有一个父亲。
1.1 树形结构的概念(重要)
重要的概念：
深度就是层数。
度就是单个节点分支的数量。
看到这里，就可以直接跳转到二叉树部分，看重点内容了。
树的以下概念只需了解，在看书时只要知道是什么意思即可：
1.2 树的表示形式（了解）
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如： 双亲表示法 ， 孩子表示法 、 孩子双亲表示法 、 孩子兄弟表示法 等等。我们这里就简单的了解其中最常用的 孩子兄弟表示法 。class Node {
int value; // 第一个孩子引用
Node firstChild; // 树中存储的数据
Node nextBrother; // 下一个兄弟引用
}
1.3 树的应用
文件系统管理（目录和文件）。
2. 二叉树（重点）
二叉树，顾名思义，每个节点度最大只有 2 的树。(每个节点最多只有两个分支的树)。
2.1 概念
一棵二叉树是节点的一个有限集合，该集合：
1. 或者为空
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
如上图，二叉树不存在度大于 2 的节点，且二叉树有左子树和右子树之分，顺序不能颠倒。
2.2 两种特殊的二叉树
1. 满二叉树：一颗二叉树，每一层节点数都达到最大值，也就是说如果一棵树有 K 层，树的节点数为 2^K - 1，则这棵树就是满二叉树。
2. 完全二叉树：对于深度为 K 的，有 n 个节点的二叉树，只有当每个节点从上到下从左到右都与深度为 K 的满二叉树中 0 - n-1 的编号 一 一 对应，才是完全二叉树。（从上到下从左到右编号与 0 - n-1 对应的就是完全二叉树）
所以说满二叉树也是一种特殊的完全二叉树。
如下图：
2.3 二叉树的性质
1. 若规定根节点的层数为1，则一棵非空二叉树的第 i 层上最多有 2^(i-1)(i>0)个节点
2. 若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大节点数是 2^k-1(k>=0)
3. 对任何一棵二叉树, 如果其叶子节点个数为 n0, 度为2的非叶子节点个数为 n2,则有n0＝n2＋1
叶子节点个数永远比度为 2 节点个数多一个。
4. 具有n个节点的完全二叉树的深度k为 log2(n+1)上取整
5. 对于具有n个节点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为 i 的节点有：
- 若i > 0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
- 若2i + 1 < n，左孩子序号：2i+1，否则无左孩子
- 若2i + 2 < n，右孩子序号：2i+2，否则无右孩子
第三条性质推导过程：
可以做一下题
1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ） A 不存在这样的二叉树 B 200 C 198 D 199 2. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ） A n B n+1 C n-1 D n/2 3. 一个具有 767 个节点的完全二叉树，其叶子节点个数为（） A 383 B 384 C 385 D 386 4. 一棵完全二叉树的节点数为 531 个，那么这棵树的高度为（ ） A 11 B 10 C 8 D 12
答案：BABB
1. n0 = n2 + 1
2.
所以 选 A，第三题同理
4. 深度 = log2(n + 1) 向上取整。 log2(532) = 9 还多，所以加1为 10.
2.4 二叉树的存储
二叉树的存储结构分为：顺序存储和类似于链表的链式存储。
二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式:
// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
Node parent; // 当前节点的根节点
}在刷算法题的时候，一般用的是孩子表示法。
2.5 二叉树的基本操作
2.5.1 二叉树的遍历
二叉树的遍历有四种：前序遍历，中序遍历，后序遍历，层序遍历。
所谓遍历，就跟数组的遍历一样，就是以某种特定的方式来访问二叉树的每一个节点，每个节点只访问一次。
先来看前序遍历.
1. 前序遍历
以根左右的方式访问每一个节点：根节点 -> 左子树的节点 -> 右子树的节点。
打印顺序：1 2 4 5 3 6 7
2. 中序遍历
以左根右的方式访问每一个节点：左子树的节点 -> 根节点 -> 右子树的节点。
打印顺序： 4 2 5 1 6 3 7
3. 后序遍历
以左右根的方式访问每一个节点：左子树的节点 -> 右子树的节点 -> 根节点。
打印顺序：4 5 2 6 7 3 1
4. 层序遍历
从上到下，一层一层地来遍历。
了解完以上内容后，可以再来做下题目。
1. 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为 ( ) A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA 2. 二叉树的先序遍历和中序遍历如下：先序遍历： EFHIGJK; 中序遍历： HFIEJKG. 则二叉树根结点为 ( ) A: E B: F C: G D: H 3. 设一课二叉树的中序遍历序列： badce ，后序遍历序列： bdeca ，则二叉树前序遍历序列为 ( ) A: adbce B: decab C: debac D: abcde 4. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出 ( 同一层从左到右 ) 的序列为 ( ) A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF
答案：AADA
1. 直接把图画出来即可。
2. 前序遍历：根左右，中序遍历：左根右，可以根据前序遍历的根来从中序遍历种找，根的左边是左子树，根的右边是右子树。前序遍历的第一个就是根，所以为 E
3. 中序：左根右，后序：左右根，所以后序遍历靠后的就是根，根据根从 中序遍历中找，根左边的就是左子树，右边的就是右子树。第 4 题同理。
根据前序和后序不能创建一颗二叉树，因为前序和后序都是确定根的位置。
2.5.2 二叉树的基本操作
我们可以尝试来实现一颗二叉树，首先创建个 BinaryTree 类，因为 二叉树是由一个个节点构成的，所以我们需要创建个内部类 TreeNode 用来作为二叉树的节点。
二叉树中一个节点包含三个部分，如图，分别是 value(值) ，left(左子树) ，right(右子树)。
二叉树还有一个属性，那就是根节点，根据以上信息，我们就可以轻松的写出二叉树的大致轮廓了。
public class BinaryTree {
static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode root;//根节点
}接下来我们还需要手动创建一颗二叉树 ，可以写一个方法来完成。
public TreeNode createTree() {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
return node1;
}可以创建个 测试类来测试看看效果。
public class Test {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.root = binaryTree.createTree();
System.out.println();
}
}
没啥问题。
接下来就可以实现二叉树的基本操作了。
// 前序遍历
public void preOrder(TreeNode root) {
}
// 中序遍历
public void inOrder(TreeNode root) {
}
// 后序遍历
public void postOrder(TreeNode root) {
}
// 获取树中节点的个数
public int size(TreeNode root) {
return -1;
}
// 获取叶子节点的个数
public int getLeafNodeCount(TreeNode root) {
return -1;
}
// 子问题思路-求叶子结点个数
// 获取第K层节点的个数
public int getKLevelNodeCount(TreeNode root, int k) {
return -1;
}
// 获取二叉树的高度
public int getHeight(TreeNode root) {
return -1;
}
// 检测值为value的元素是否存在
public boolean find(TreeNode root, int val) {
return false;
}
//层序遍历
public void levelOrder(TreeNode root) {
}
// 判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root) {
return false;
}把上面代码拷贝到 BinaryTree 中，然后再一一实现即可。
首先来写前中后序遍历的实现，这三个都比较简单，就是访问根节点的时机不同。
用递归实现，首先我们要相信 preOrder() 一定会帮我们完成前序遍历这个任务，然后我们再来思考递归的出口是什么？啥时候可以不用遍历，直接就返回？
那当然是根节点为空的时候，二叉树为空，就不用打印了，直接返回。
然后再思考子问题的解决过程，这个也很简单，那就是每一个节点都要按照根左右的方式来遍历。至此，我们就可以开始写代码了。
中序遍历和后序遍历同理，只需要将 访问根节点的时机改一下即可。
这样，前中后序遍历就写好了。
// 前序遍历
public void preOrder(TreeNode root) {
// 二叉树为空
if (root == null) return;
// 根左右
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历
public void inOrder(TreeNode root) {
// 二叉树为空
if (root == null) return;
// 左根右
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
// 后序遍历
public void postOrder(TreeNode root) {
// 二叉树为空
if (root == null) return;
// 左右根
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}写完后可以测试看看。
public class Test {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.root = binaryTree.createTree();
System.out.println("前序遍历：");
binaryTree.preOrder(binaryTree.root);
System.out.println();
System.out.println("中序遍历：");
binaryTree.inOrder(binaryTree.root);
System.out.println();
System.out.println("后序遍历：");
binaryTree.postOrder(binaryTree.root);
}
}
我们还可以再写一种，将前序遍历的结果返回。
这个和刚刚的前序遍历写的一摸一样，只不过是吧方法的返回值存起来罢了。
然后再来实现 size 方法，计算二叉树节点个数。这个也很简单，直接遍历二叉树，然后遇到一个节点，计数器就++。也可能用子问题的思路来写，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1（自己本身）。
// 获取树中节点的个数
public int size(TreeNode root) {
if (root == null) return 0;
return size(root.left) + size(root.right) + 1;
}
// 获取树中节点的个数
public int count = 0;
public int size2(TreeNode root) {
if (root == null) return 0;
count++;
size2(root.left);
size2(root.right);
return count;
}写完后测试下看看。
没啥问题。
然后我们来写 getLeafNodeCount 方法，获取叶子节点个数，叶子节点就是度为 0 的节点，left 和 right 都为 null。我们可以遍历二叉树，如果遇到 left 和 right 同时为空的节点，就计数器++。
或者我们也可以用子问题的思路：二叉树叶子节点个数 = 左子树叶子节点 + 右子树叶子节点
// 获取叶子节点的个数
public int getLeafNodeCount(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
// 获取叶子节点的个数
public int leafSize = 0;
public int getLeafNodeCount2(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) {
leafSize++;
}
getLeafNodeCount2(root.left);
getLeafNodeCount2(root.right);
return leafSize;
}写完后，我们可以测试下看看。
没问题，接下来可以去写 getKLevelNodeCount 方法。获取第 K 层的节点个数。
// 子问题思路-求叶子结点个数
// 获取第K层节点的个数
public 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);
}写获取 K 层节点数后，可以测试下看看。
没问题，可以去写 getHeight 方法了 。
获取二叉树的高度，就是获取二叉树一共有几层，还是用子问题的思路，
树的高度 = MAX（左子树的高度，右子树的高度）+ 1（本身的高度）
根据以上信息，就可以写出代码。
测试下看看。
没问题接下来就可以去写 find，在二叉树中查找指定值的方法了。
这个很简单，遍历二叉树，找到了返回 true，没找到返回 false 即可。
写完后来看看效果。
接下来就可以去写 levelOrder 方法了。
层序遍历，就是从上到下按层依次遍历。
可以使用队列(先进先出)的方式来存储二叉树的每一个节点，弹出一个节点，如果不为空，就将 left 和 right 放进去，然后打印这个节点的值，当队列里没有元素时，就遍历完了。
根据上面的流程图，其实我们还能获取到二叉树每一层的节点，只要在进入队列的时候看看还剩几个节点，然后出队几次，就能获取到该层的所有节点了。
//层序遍历
public void levelOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.print(cur.val + " ");
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}写完后来测试一下看看。
没问题，接下来可以去写 isCompleteTree 方法了。
判断是否是完全二叉树，其实这个也简单。如图，下面那个就是完全二叉树，只要判断在最后一个节点之后还有没有节点，也就是判断最后一个节点后面是否全是空即可。
还是可以利用刚刚的层序遍历，判断出队元素是否为空，如果为空，那么一直出队，看看出队元素是否非空，非空就返回 false，如果出到队列为空了还没碰见非空元素，则说明就是完全二叉树，返回 true 即可。
// 判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root) {
//空树
if (root == null) {
return true;
}
//完全二叉树是从左到右连续存放的二叉树
//利用队列实现，弹出队头元素cur，如果cur元素是null，
//则判断队列里的元素是否全是null，如果含有不为空的元素，则说明不是完全二叉树
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur != null) {
queue.add(cur.left);
queue.add(cur.right);
} else {
//证明此时遇到了null
break;
}
}
//不能用isEmpty()来判断队列里面是否全是null
//得一个个手动判断
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur != null) {
//说明二叉树不是连续存放的
return false;
}
}
return true;
}测试下看看。
没啥问题，到这里二叉树的基本操作就写完了。
BinaryTree 类
import java.util.*;
public class BinaryTree {
static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode root;//根节点
public TreeNode createTree() {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
return node1;
}
// 前序遍历
public void preOrder(TreeNode root) {
// 二叉树为空
if (root == null) return;
// 根左右
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
//将前序遍历的结果存储到list当中
public List<TreeNode> preOrder2(TreeNode root) {
List<TreeNode> ret = new ArrayList<>();
if (root == null) {
return ret;
}
// 根左右
ret.add(root);
//System.out.print(root.val + " ");
// 得到左子树的返回值
List<TreeNode> left = preOrder2(root.left);
ret.addAll(left);
// 得到右子树的返回值
List<TreeNode> right = preOrder2(root.right);
ret.addAll(right);
return ret;
}
// 中序遍历
public void inOrder(TreeNode root) {
// 二叉树为空
if (root == null) return;
// 左根右
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
// 后序遍历
public void postOrder(TreeNode root) {
// 二叉树为空
if (root == null) return;
// 左右根
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
// 获取树中节点的个数
public int size(TreeNode root) {
if (root == null) return 0;
return size(root.left) + size(root.right) + 1;
}
// 获取树中节点的个数
public int count = 0;
public int size2(TreeNode root) {
if (root == null) return 0;
count++;
size2(root.left);
size2(root.right);
return count;
}
// 获取叶子节点的个数
public int getLeafNodeCount(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
// 获取叶子节点的个数
public int leafSize = 0;
public int getLeafNodeCount2(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) {
leafSize++;
}
getLeafNodeCount2(root.left);
getLeafNodeCount2(root.right);
return leafSize;
}
// 子问题思路-求叶子结点个数
// 获取第K层节点的个数
public 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);
}
// 获取二叉树的高度
public int getHeight(TreeNode root) {
if (root == null) return 0;
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
// 检测值为value的元素是否存在
public boolean find(TreeNode root, int val) {
if (root == null) return false;
if (root.val == val) return true;
return find(root.left, val) || find(root.right, val);
}
//层序遍历
public void levelOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.print(cur.val + " ");
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}
// 判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root) {
//空树
if (root == null) {
return true;
}
//完全二叉树是从左到右连续存放的二叉树
//利用队列实现，弹出队头元素cur，如果cur元素是null，
//则判断队列里的元素是否全是null，如果含有不为空的元素，则说明不是完全二叉树
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur != null) {
queue.add(cur.left);
queue.add(cur.right);
} else {
//证明此时遇到了null
break;
}
}
//不能用isEmpty()来判断队列里面是否全是null
//得一个个手动判断
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur != null) {
//说明二叉树不是连续存放的
return false;
}
}
return true;
}
}Test 类
public class Test {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.root = binaryTree.createTree();
System.out.println("前序遍历：");
binaryTree.preOrder(binaryTree.root);
System.out.println();
System.out.println("中序遍历：");
binaryTree.inOrder(binaryTree.root);
System.out.println();
System.out.println("后序遍历：");
binaryTree.postOrder(binaryTree.root);
System.out.println();
System.out.println("二叉树节点数量1：" + binaryTree.size(binaryTree.root));
System.out.println("二叉树节点数量2：" + binaryTree.size2(binaryTree.root));
System.out.println();
System.out.println("二叉树叶子节点数量1：" + binaryTree.getLeafNodeCount(binaryTree.root));
System.out.println("二叉树叶子节点数量2：" + binaryTree.getLeafNodeCount2(binaryTree.root));
System.out.println("第3层节点个数：" + binaryTree.getKLevelNodeCount(binaryTree.root, 3));
System.out.println("二叉树的高度：" + binaryTree.getHeight(binaryTree.root));
System.out.println(binaryTree.find(binaryTree.root, 5));
System.out.println("层序遍历：");
binaryTree.levelOrder(binaryTree.root);
System.out.println();
boolean completeTree = binaryTree.isCompleteTree(binaryTree.root);
System.out.println("是否是完全二叉树: " + completeTree);
}
}
2.6 二叉树面试题
还可以根据上面学的知识点来刷下题，二叉树的题 一般都是用递归来完成。
1.检查两棵树是否相同
如图，题目要求让我们判断两棵树是否相同，并给出明确的相同的定义：
1. 结构相同
2. 值相同
我们可以用递归来做，
树相同 = 结构相同并且值相同的根节点 + 左子树相同 + 右子树相同。
这样，我们就可以写题了，还要考虑两颗树都为空，那也相同。
代码实现：
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if ((p == null && q != null) || (p != null && q == null)) {
// 结构不同
return false;
}
if (p.val != q.val) {
// 值不同
return false;
}
// 到了这里说明根节点是相同的，还需要判断左子树和右子树
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
2.另一棵树的子树
你看到这道题的第一个示例，有没有感觉跟刚刚我们写的 “判断两棵树是否是相同的子树” 很像？
觉得像就对了，就是差不多的，就是找相同子树嘛，每个节点都去判断一下是否是相同的树就好了。
代码实现：
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) return true;
else if (root == null) return false;
// 如果两棵树相同
if (isSameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null && q != null || p != null && q == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
3.翻转二叉树
这道题也挺简单的，还是用递归，翻转二叉树 = 翻转二叉树的左子树 + 翻转二叉树的右子树
就是交换左右孩子节点嘛, 我用的前序遍历。
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
// 遍历，交换
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
4.平衡二叉树
给了平衡二叉树的解释，左右子树高度差超过 1 说明就不平衡了。
可以直接判断整棵树的高度是否平衡 = 左子树的高度平衡 + 右子树的高度平衡，用递归，先写出求树的高度的方法，然后用递归求每棵子树的高度是否平衡即可。
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (Math.abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
public int getHeight(TreeNode root) {
if (root == null) return 0;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
还可以有改进的方法，那就是在计算高度的时候顺便判断高度是否平衡。
如果不平衡，那就高度返回 -1，平衡才正常返回高度。
优化：
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return getHeight(root) >= 0;
}
public int getHeight(TreeNode root) {
if (root == null) return 0;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {
return Math.max(leftHeight, rightHeight) + 1;
}
return -1;
}
}
5.对称二叉树
判断二叉树是否对称 = 左子树对称 + 右子树对称。
对称：1. 结构相同，2. 值对称。
跟之前写的二叉树相同有点像。
因为有两个参数，所以需要新写一个方法。
代码实现：
class Solution {
public boolean isSymmetric(TreeNode root) {
return isSymmetric(root.left, root.right);
}
public boolean isSymmetric(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null && q != null || p != null && q == null) {
return false;
}
if (p.val != q.val) return false;
// 对称
return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
}
}
6.二叉树遍历
这个也不算难，他给你的是前序遍历的字符串，那我们就可以根据前序遍历的方式来创建二叉树。
还是先搭建好二叉树的节点框架，然后再写中序遍历，最后写创建二叉树即可。
代码实现：
import java.util.Scanner;
class TreeNode {
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { //有空格
String str = in.nextLine();
TreeNode root = createTree(str);
inorder(root);//中序遍历
}
}
//用i遍历str
public static int i = 0;
public static TreeNode createTree(String str) {
TreeNode root = null;
char ch = str.charAt(i);
//如果ch不是#,就说明ch是一个节点
//我们利用前序遍历的方式创建二叉树
//根 左 右
if (ch != '#') {
root = new TreeNode(ch);
i++;
//然后 递归
root.left = createTree(str);
root.right = createTree(str);
} else {
//如果是#，就跳过
i++;
}
return root;//返回创建好的树
}
public static void inorder(TreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
}
7.二叉树的层序遍历
之前已经讲过了，不再赘述，用队列即可实现。
代码实现：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if (root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
// 获取这一层的节点个数
int size = queue.size();
List<Integer> tmp = new ArrayList<>();
while (size != 0) {
TreeNode cur = queue.poll();
tmp.add(cur.val);
if (cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
size--;
}
// 到这里，这一层的元素就处理完了
ret.add(tmp);
}
return ret;
}
}
8.二叉树的最近公共祖先
求最近的公共祖先，得画图分析，分以下三种情况。
了解上面信息之后，就可以通过递归来写，用前序遍历，先看根节点，再看左边和右边，如果左右都存在，说明在两边，返回 root，如果左边在，返回左边，如果右边在，返回右边。
代码实现：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
// 根左右遍历
if (p == root || q == root) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
// 说明 p 和 q 在 root 的左子树和右子树
return root;
} else if (left != null) {
// p 和 q 在 root 的左边,
return left;
} else {
// // p 和 q 在 root 的右边
return right;
}
}
}