目录
1、题一：检查两棵树是否相同
1.1 思路分析
两颗树相同，需要注意以下几点：
- 两颗树结构相同，若结构不相同，那两棵树必然是不相同的
- 在结构相同的前提下，还需满足节点值相同
- 若结构和节点值都相同，那么两棵树相同
额外注意的是：若两颗树为空，那么也是相同的。
我们可以按照子问题遍历的思想，当左子树和右子树的中的全部节点同时满足以上条件，说明两棵树相等。
1.2 代码
时间复杂度：O（min（m,n））
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;
}
//走到这里，说明两颗树的结构相同且不为空，那判断他们的节点值即可
//若节点值不相同，则说明两棵树不相同，返回false
if(p.val != q.val) {
return false;
}
//递归遍历
//左右两颗子树必须同时满足条件
//才能说明两颗树才相同
return isSameTree(p.left,q.left) &&
isSameTree(p.right,q.right);
}
}2、题二：另一颗树的子树
2.1 思路分析
一颗树的子树 需要满足：
- 这颗子树包括主树的某个节点，和这个节点的所有后代节点
- 这颗树自身，也可看做自己的子树
了解子树概念后，我们可以按照以下思路解决问题：
- 判断子树根节点subRoot和主树根节点root是否相同
- 若相同，则调用检查两棵树是否相同的方法（题一），若相同，则为子树
- 若不相同，继续遍历，判断子树是否和root的左子树相同
- 若不相同，继续遍历，判断子树是否和root的右子树相同
- 递归解决问题
2.2 代码
时间复杂度：O(m*n)
因为最坏的情况下：
每个节点和子树值相同，但判断树是否相同时，总是最后一个节点不相同
/**
时间复杂度为：O(m*n)
因为最坏的情况下：
每个节点和子树值相同，但判断树是否相同时，总是最后一个节点不相同
*/
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//如果递归到空，说明没有找到子树，返回false
if(root == null) {
return false;
}
//判断当前节点的整颗树和子树是否相同即可
if(isSameTree(root,subRoot)) {
return true;
}
//如果递归遇见了子树 则一路返回true
if(isSubtree(root.left,subRoot)) return true;
if(isSubtree(root.right,subRoot)) return true;
//本次递归没有找见子树 返回false
return false;
}
public boolean isSameTree(TreeNode p, TreeNode q) {
// 1.先判断结构是否是一样的
if (p != null && q == null || p == null && q != null) {
return false;
}
// 上述if语句 如果没有执行，意味着两个引用 同时为空 或者同时不为空
if (p == null && q == null) {
return true;
}
// 都不为空 判断值是否一样
if (p.val != q.val) {
return false;
}
// 都不为空且值一样
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}3、题三：翻转二叉树
3.1 思路分析
这道题的思路很简单，就是：将每个节点的左右子树进行交换。
我们可以以前序遍历思想遍历所有节点，在访问当前树的根节点时将其左右子树进行交换。
3.2 代码
根据解题思想，很清晰的分析出时间复杂度为：O（n）
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
//交换左右子树
swapNode(root);
invertTree(root.left);
invertTree(root.right);
return root;
}
public void swapNode(TreeNode root) {
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}
}4、题四：判断树是否对称
4.1 思路分析
要判断这颗树是对称的，
- 就要判断，根节点的左子树和右子树是对称的
- 要判断根节点的左子树和右子树是对称的 ，需要左右子树的结构相同；在结构相同前提下，节点的值要相同
- 如果结构相同了，值也相同了，那么要递归去判断：左子树的左树和右子树的右树是否轴对称（是否结构相同、值相同）；以及左子树的右树和右子树的左树是否轴对称（是否结构相同、值相同）。（均满足）
- 我们只能递归来一个节点一个节点的去遍历，去判断，去比较
4.2 代码
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}
return isSymmetricChild(root.left,root.right);
}
public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
//空树对称
if(leftTree == null && rightTree == null) {
return true;
}
//结构不相同 必定不对称
if(leftTree != null && rightTree == null ||
leftTree == null && rightTree != null) {
return false;
}
//节点值不相同 必定不对称
if(leftTree.val != rightTree.val) {
return false;
}
//左子树的左树和右子树的右树
//左子树的右树和右子树的左树
//都要对称
return isSymmetricChild(leftTree.left,rightTree.right)
&& isSymmetricChild(leftTree.right,rightTree.left);
}
}5、题五：判断是否为平衡二叉树
5.1 思路分析
5.1.1 平衡二叉树概念
如果一颗树是平衡二叉树，那么满足：
- 树中所有节点的左右子树高度差<=1
- 也就是说，每一颗子树都是平衡二叉树
根据平衡二叉树的概念，我们有以下两种思路解决问题。
5.1.2 思路一 O(n^2)
- 递归遍历所有节点，求出每个节点的左右子树高度差，若出现>=2的情况，立即返回false
- 当前节点的左树上的节点和右树上的节点全部满足高度差<=1 时，说明为平衡二叉树
- 该思路时间复杂度为O（n^2），求根节点高度的方法时间复杂度本来就为O（n），而要求得所有节点的高度，时间复杂度就为O（n^2）
5.1.3 思路一代码
class Solution {
public boolean isBalanced(TreeNode root) {
//空树 平衡
if(root == null) {
return true;
}
//当前节点左子树高度
int h1 = getHeight(root.left);
//当前节点右子树高度
int h2 = getHeight(root.right);
int h = Math.abs(h1-h2);//高度差
//不平衡
if(h >= 2) 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);
//树的高度为 左子树高度和右子树高度的最大值+节点自身的1个高度
return leftHeight > rightHeight
? leftHeight + 1
: rightHeight + 1;
}
}5.1.4 思路二 ：改善为O(n)【字节跳动面试题】
思路一虽然能解决问题，但时间复杂度达到了O(n^2)，并且产生了很多次重复的计算,例如：圈中节点的高度，在计算它祖先的高度时就被计算了多次，产生了很多重复的计算。
如果要将时间复杂度改善为O(n)，该如何完成呢？
O(n)思路分析：
- 我们可以只求根节点的高度
- 在求节点高度时，我们使用递归遍历思想，返回的是左右子树高度的最大值+1（左右子树最大高度+节点自身1个高度）
- 而我们可以将求高度的方法进行改善，在递归过程中，一旦发现左右子树高度差绝对值>=2时（说明不平衡），立即返回负数（标记，其他标记也可）；如果高度差绝对值<=1时（说明平衡），返回正常的高度值即可。如若发现返回的是负数，立即一路返回负数。
- 最终判断方法的返回值即可，若为负数，则说明该树不平衡；若为正数（高度值），说明该树平衡。
5.1.5 思路二代码
class Solution {
/**
时间复杂度：O（n）
*/
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);
//如若发现返回的是负数，则说明该树一定不平衡，一路返回负数
if(leftHeight < 0) {
return -1;
}
//如若发现返回的是负数，则说明该树一定不平衡，一路返回负数
int rightHeight = getHeight(root.right);
if(rightHeight < 0) {
return -1;
}
//如果绝对值<=1 说明当前树平衡，返回高度值
if(Math.abs(leftHeight - rightHeight) <= 1) {
return Math.max(leftHeight , rightHeight) + 1;
}else {
//否则返回负数
return -1;
}
}
}6、题六：将二叉搜索树转化为有序的双向链表
6.1 二叉搜索树的性质
二叉搜索树，又称二叉排序树、二叉查找树，具有以下性质：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 二叉搜索树可以为空树
- 以中序遍历来遍历一颗二叉搜索树，那么得到的序列就是一个有序的升序序列。
6.2 思路分析
以中序遍历递归这颗二叉搜索树，将得到的根节点依次连接（修改其左右指针），得到的就是排好序的双向链表。
- 借助中序遍历思想递归，遍历各个节点，修改指向
- 将每个节点的left域当做双向链表中的prev域，将right域当做next域
- 借助一个成员变量prev，存储上一个节点的地址，完成各节点指向的修改和连接
6.3 代码
时间复杂度：O（n）
public class Solution {
//定义一个成员变量 存储上一个节点的地址
TreeNode prev;//初始值为null
public void ConvertNode(TreeNode pRootOfTree) {
if(pRootOfTree == null) return;
//中序遍历思想递归
ConvertNode(pRootOfTree.left);
//修改前驱，将当前节点的left域更改为前一个节点的地址
pRootOfTree.left = prev;
if (prev != null) {
//当prev不为空时，修改后继
//将其right域修改为当前节点的地址（prev本就是当前节点的前驱）
prev.right = pRootOfTree;
}
//更新prev
prev = pRootOfTree;
ConvertNode(pRootOfTree.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) {
return null;
}
ConvertNode(pRootOfTree);
TreeNode head = pRootOfTree;
//找头结点
//转换成双向链表后，链表的头结点就在pRootOfTree的左边
//头结点的left（前驱）为null
while(head.left != null) {
head = head.left;
}
return head;
}
}7、题七：二叉树的遍历和构建
7.1 思路分析
我们知道，如果仅仅根据一个遍历方式的结果是无法构建出一颗二叉树的，必须有两个遍历方式且必须包含中序遍历。
而这道题是不同的，因为题目给出的遍历结果包含了空树，所以仅仅利用一个遍历方式我们就可以构建出二叉树。
只要构建出这颗二叉树，我们再使用中序遍历递归打印节点值就可以了。
难点在，如何使用代码根据前序遍历来构建二叉树？
思路如下：
- 题目仅仅给出了main方法，意味着我们要自己创建节点，创建的节点类要满足树中节点的要求，包含val域（char类型）、left域、right域，同时要给出构造方法
- 创建二叉树，肯定是要遍历前序遍历结果的字符串（这里以静态i成员遍历字符串）
- 给出的是前序遍历结果，所以要以前序遍历的思想递归来创建树
- 如果遍历到的字符不是'#'，说明不是空树，实例出该值的节点，i++（此时仅仅实例节点，各节点间并没有连接）
- 创建左子树，创建右子树
- 如果遇到的字符是'#'，说明遇到是空树，i++，返回空节点（递归回退），上一个节点的left或者right接收
- 如果节点的左子树或者右子树创建完成，递归回退，上一个节点的left或者right接收
- 如果节点的左子树和右子树都创建完成（本次递归函数结束），递归回退，上一个节点的left或者right接收
- 也就是说，我们在递归回退的过程中，完成节点之间的连接
- 最后一步，以中序遍历形式来访问根节点并打印
注意：这里因为题目条件限制，只能使用静态成员i来遍历字符串。但是对于我们实际的应用，不建议使用静态成员，因为当创建多个对象时，他们都会使用并改变i的值，而创建二叉树时，必须从0下标处遍历字符串！！！
7.2 代码
import java.util.Scanner;
//节点
class TreeNode {
TreeNode left;
TreeNode right;
char val;
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()) { // 注意 while 处理多个 case
//防止有多组测试用例，每次使用时i要置0
Main.i = 0;
String str = in.nextLine();
TreeNode root = creatTree(str);
InOrder(root);
}
}
public static int i;
public static TreeNode creatTree(String str) {
TreeNode node = null;
if (str.charAt(i) != '#') {
//不是空树，就实例化该值的节点
node = new TreeNode(str.charAt(i));
i++;
//在递归回退的过程中，完成节点之间的连接
node.left = creatTree(str);
node.right = creatTree(str);
} else {
//是空树，i++
i++;
}
return node;
}
//中序遍历，打印根节点
public static void InOrder(TreeNode root) {
if (root == null) {
return;
}
InOrder(root.left);
System.out.print(root.val + " ");
InOrder(root.right);
}
}