二叉树LeetCode刷题
- 1. 检查两颗树是否相同
- 2. 另一颗树的子树
- 3. 翻转二叉树
- 4. 判断一颗二叉树是否是平衡二叉树
- 5. 二叉搜索树与双向链表
- 6. 对称二叉树
- 7. 二叉树的构建及遍历
- 8. 二叉树的分层遍历
- 9. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
- 10. 根据一棵树的前序遍历与中序遍历构造二叉树
- 11. 根据一棵树的中序遍历与后序遍历构造二叉树
- 12. 二叉树创建字符串
- 13. 二叉树前序非递归遍历实现
- 14. 二叉树中序非递归遍历实现
- 15. 二叉树后序非递归遍历实现
1. 检查两颗树是否相同
题目链接：100. 相同的树
解题思路：
- 判断两棵树的结构是否相同，若结构都不相同，则肯定不相同
- 判断两棵树的根节点对应的值是否相同，不相同则返回false，相同则去判断左右子树是否是相同的树
代码如下：
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
//判断结构是否相同
if(p == null && q != null) {
return false;
}
if(p != null && q == null) {
return false;
}
if(p == null && q == null) {
return true;
}
//判断值是否相同
if(p.val == q.val) {
//值相同则去判断左右子树是否相同
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
return false;
}
}
2. 另一颗树的子树
题目链接：572. 另一棵树的子树
解题思路：
- 判断原树是否与该树相同，若不相同，则递归判断原树的子树是否与该树相同
- 需要用到上面判断两棵树是否相同的代码
代码如下：
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
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 false;
}
if(p != null && q == null) {
return false;
}
if(p == null && q == null) {
return true;
}
//判断值是否相同
if(p.val == q.val) {
//值相同则去判断左右子树是否相同
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
return false;
}
}
3. 翻转二叉树
题目链接：226. 翻转二叉树
解题思路1：
- 创建一个临时变量，用来交换左右子树
- 从树的上部依次往下交换左右子树的根节点，不断往树的深层次递归，直至为空或叶子节点
代码如下：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
//叶子节点后的节点为null,无需再交换
if(root.left == null && root.right == null) {
return root;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
解题思路2：
- 利用返回值
- 采用后序遍历，从树的底部往顶部依次交换左右子树的根节点
- 需要将左右子树根节点利用返回值记录下来，便于后续对原树的左右子树节点的更改
代码如下：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
if(root.left == null && root.right == null) {
return root;
}
TreeNode leftTree = invertTree(root.left);
TreeNode rightTree = invertTree(root.right);
root.left = rightTree;
root.right = leftTree;
return root;
}
}
4. 判断一颗二叉树是否是平衡二叉树
题目链接：110. 平衡二叉树
平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1
解题思路1：
- 分别获取左右子树的高度，作差，如果该树的任意一棵子树的左右子树高度差都小于等于1，则是一棵平衡树，反之则不是
代码如下：
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
int leftTreeHeight = getHeight(root.left);
int rightTreeHeight = getHeight(root.right);
if(Math.abs(leftTreeHeight-rightTreeHeight) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
private int getHeight(TreeNode root) {
if(root == null) {
return 0;
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
}
该算法的时间复杂度为：O(N2)
解题思路2：
- 思路1是从原树往树的深层入手，会重复运算后续子树的高度，因此时间复杂度会达到O(N2)；换个思路，从树的最底层往根节点入手，那么时间复杂度就会大大减少
- 每次将返回的左右子树高度作差，如果小于等于1，则将当前树的高度；如果大于1，则返回-1，作为标记
代码如下：
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) >= 0;
}
public int getHeight(TreeNode root) {
if(root == null) return 0;
int leftTreeHeight = getHeight(root.left);
if(leftTreeHeight < 0) {
return -1;
}
int rightTreeHeight = getHeight(root.right);
if(rightTreeHeight < 0) {
return -1;
}
if(Math.abs(leftTreeHeight - rightTreeHeight) <= 1) {
return Math.max(leftTreeHeight, rightTreeHeight) + 1;
}else {
return -1;
}
}
}
5. 二叉搜索树与双向链表
题目链接：二叉搜索树与双向链表
解题思路：
- 当二叉搜索树进行中序遍历时，得到的是一个有序的结果
- 那么，可以对二叉搜索树进行中序遍历，并用每个子树根节点的left指向前一个节点，right指向后一个节点，这里的前一个节点和后一个节点是转化成双向链表后，该节点的前一个节点和后一个节点
代码如下：
public class Solution {
TreeNode prev;//记录前一个节点
TreeNode head;//记录双向链表的头节点
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return null;
}
Convert(pRootOfTree.left);
//指向修改操作
if(prev == null) {
prev = pRootOfTree;
head = pRootOfTree;
}else {
pRootOfTree.left = prev;
prev.right = pRootOfTree;
prev = pRootOfTree;
}
Convert(pRootOfTree.right);
return head;
}
}
6. 对称二叉树
题目链接：101. 对称二叉树
解题思路：
- 3.1是判断两棵树是否相同，现在是判断一棵树是否对称，只需将对3.1中的代码进行修改即可
- 判断这棵树的左子树的根节点值和右子树的根节点值是否相同，不断往深层递归
代码如下：
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}
return isSameTree(root.left, root.right);
}
private boolean isSameTree(TreeNode p, TreeNode q) {
if(p != null && q == null) {
return false;
}
if(p == null && q != null) {
return false;
}
if(p == null && q == null) {
return true;
}
if(p.val != q.val){
return false;
}
return isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
}
}
7. 二叉树的构建及遍历
题目链接：KY11 二叉树遍历
解题思路：
- 利用先序遍历的字符串创建树，如果是#，则返回null；如果不是#，则该字符创建为根节点，再去递归去创建左子树和右子树，最后返回根节点
- 中序遍历这棵树
代码如下：
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()) { // 注意 while 处理多个 case
String str = in.nextLine();
TreeNode root = createTree(str);
inOrder(root);
}
}
public static int i = 0;
public static TreeNode createTree(String str) {
char ch = str.charAt(i);
if(ch == '#') {
i++;
return null;
}else {
TreeNode root = new TreeNode(ch);
i++;
root.left = createTree(str);
root.right = createTree(str);
return root;
}
}
public static void inOrder(TreeNode root) {
if(root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
但是上述代码存在一点小问题：由于i是静态成员变量，在输入第一次测试用例ABC##DE#G##F###后，如果后续再输入第二组测试用例，i的值是从9开始的，这是不对的，应该是从0开始的，因此需要进行调整，调整方式有如下两种
- 每次循环最后将i的值更改为0
代码如下：
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()) { // 注意 while 处理多个 case
String str = in.nextLine();
TreeNode root = createTree(str);
inOrder(root);
i = 0;
}
}
public static int i = 0;
public static TreeNode createTree(String str) {
char ch = str.charAt(i);
if(ch == '#') {
i++;
return null;
}else {
TreeNode root = new TreeNode(ch);
i++;
root.left = createTree(str);
root.right = createTree(str);
return root;
}
}
public static void inOrder(TreeNode root) {
if(root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
- 将静态变量i和静态方法createTree改为非静态的，那么在静态方法main中，就需要实例化Main对象，进而去调用非静态方法createTree
注：
- 在静态方法的内部不能直接调用非静态方法，因为方法属于类而不是对象，我们可以通过自己手动new对象来在静态方法中调用
代码如下：
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()) { // 注意 while 处理多个 case
String str = in.nextLine();
TreeNode root = new Main().createTree(str);
inOrder(root);
}
}
public int i = 0;
public TreeNode createTree(String str) {
char ch = str.charAt(i);
if(ch == '#') {
i++;
return null;
}else {
TreeNode root = new TreeNode(ch);
i++;
root.left = createTree(str);
root.right = createTree(str);
return root;
}
}
public static void inOrder(TreeNode root) {
if(root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
8. 二叉树的分层遍历
题目链接：102. 二叉树的层序遍历
解题思路：
- 大致与前面的层序遍历相同，只不过，这道题需要将每一层的元素放入一个“数组”，再将各个“数组”组和，构成一个“二维数组”
代码如下：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new LinkedList<>();
if(root == null) {
return ret;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();//size即每一层的元素个数
List<Integer> list = new LinkedList<>();
while(size != 0) {
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
size--;
}
ret.add(list);
}
return ret;
}
}
9. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
题目链接：236. 二叉树的最近公共祖先
思路1：
这两个节点无外乎有三种情况：
- p和q分别分布在root的左子树和右子树
这时，p和q的最近公共祖先就是root - p或q与root指向同一个节点
这时，p和q的最近公共祖先就是root - p和q都在root的左子树（或右子树）上
这时，往root的左子树（或右子树）递归
代码如下：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return root;
}
if(p == root || q == root) {
return root;
}
TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
if(leftTree != null && rightTree != null) {
return root;
}else if(leftTree == null) {
return rightTree;
}else {
return leftTree;
}
}
}
思路2：
分别找到根节点到p和q的路径，然后求这两条路径的交点，即为p和q的最近公共祖先
问题的关键就是如何找到这条路径
- 首先需要创建一个栈来保存路径
- 直接将root节点放入栈种，后续若发现该节点不是路径上的节点，再将其弹出，
- 判断root节点是否是p节点，如果是，则直接返回true；如果不是，再分别从root节点的左子树和右子树上去找p节点
- 如果最后还是没有找到，说明当前的root节点不是路径上的节点，将其弹出，并返回false
找到root节点到p和q的路径后，如何求交点呢？只需将路径长的元素对应的栈，先出栈大小差值个元素，再将两个栈同时进行出栈操作，直至遇到出栈元素相同时，这时出栈的元素就是p和q最近的公共祖先
代码如下：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return root;
}
Stack<TreeNode> stackP = new Stack<>();
Stack<TreeNode> stackQ = new Stack<>();
getPath(root, p, stackP);
getPath(root, q, stackQ);
int sizeP = stackP.size();
int sizeQ = stackQ.size();
if(sizeP > sizeQ) {
int size = sizeP - sizeQ;
while(size-- != 0) {
stackP.pop();
}
}else {
int size = sizeQ - sizeP;
while(size-- != 0) {
stackQ.pop();
}
}
while(!stackP.isEmpty()) {
if(stackP.peek() == stackQ.peek()) {
return stackP.peek();
}else {
stackP.pop();
stackQ.pop();
}
}
return null;
}
private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
if(root == null) {
return false;
}
stack.push(root);
if(root == node) {
return true;
}
boolean ret = getPath(root.left, node, stack);
if(ret) {
return true;
}
ret = getPath(root.right, node, stack);
if(ret) {
return true;
}
stack.pop();
return false;
}
}
10. 根据一棵树的前序遍历与中序遍历构造二叉树
题目链接：105. 从前序与中序遍历序列构造二叉树
解题思路：
- 前序遍历是用来确定根节点的，中序遍历是用来建立左子树和右子树的
- 在前序遍历中，用一个变量preIndex来获取根节点；在中序遍历中，用rootIndex来标记根节点的位置，inorderBegin标记建树的起始位置，inorderEnd标记建树的终止位置
- 先初始化根节点，再去建立左子树和右子树，不难发现：inorderBegin = rootIndex-1，inorderEnd = rootIndex+1
于是，可以写出大体结构
TreeNode root = new TreeNode(preorder[preIndex]);
preIndex++;
//由于前序遍历顺序是：根->左->右，所以创建完根以后，应该先创建左子树，再创建右子树
root.left = buildTreeChild(preorder, preIndex, inorder, inBegin, rootIndex - 1);
root.right = buildTreeChild(preorder, preIndex, inorder, rootIndex + 1, inEnd);
再进行补充，根据思路写出的代码：
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder, 0, inorder, 0, inorder.length - 1);
}
private TreeNode buildTreeChild(int[] preorder, int preIndex, int[] inorder, int inBegin, int inEnd) {
if (inBegin > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preIndex]);
int rootIndex = findVal(inorder, inBegin, inEnd, preorder[preIndex]);
preIndex++;
root.left = buildTreeChild(preorder, preIndex, inorder, inBegin, rootIndex - 1);
root.right = buildTreeChild(preorder, preIndex, inorder, rootIndex + 1, inEnd);
return root;
}
private int findVal(int[] inorder, int inBegin, int inEnd, int val) {
for (int i = inBegin; i <= inEnd; i++) {
if (inorder[i] == val) {
return i;
}
}
return -1;
}
}
但是，这个代码存在一个特别隐蔽的问题：每次回归，preIndex的值同样会回归到原来的值，而按照我们的思路，preIndex是一直往前走的，不能回退。因此，我们需要将preIndex设置为成员变量
完善后的代码如下：
class Solution {
public int preIndex;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
}
private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegin, int inEnd) {
if (inBegin > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preIndex]);
int rootIndex = findVal(inorder, inBegin, inEnd, preorder[preIndex]);
preIndex++;
root.left = buildTreeChild(preorder, inorder, inBegin, rootIndex - 1);
root.right = buildTreeChild(preorder, inorder, rootIndex + 1, inEnd);
return root;
}
private int findVal(int[] inorder, int inBegin, int inEnd, int val) {
for (int i = inBegin; i <= inEnd; i++) {
if (inorder[i] == val) {
return i;
}
}
return -1;
}
}
11. 根据一棵树的中序遍历与后序遍历构造二叉树
题目链接：106. 从中序与后序遍历序列构造二叉树
解题思路大致与前面那题差不多，但也有一些区别
代码如下：
class Solution {
public int postIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postIndex = postorder.length - 1;//后序遍历确定根，需要从后往前
return buildTreeChild(postorder, inorder, 0, inorder.length - 1);
}
private TreeNode buildTreeChild(int[] postorder, int[] inorder, int inBegin, int inEnd) {
if (inBegin > inEnd) {
return null;
}
TreeNode root = new TreeNode(postorder[postIndex]);
int rootIndex = findVal(inorder, inBegin, inEnd, postorder[postIndex]);
postIndex--;
//由于后序遍历顺序是：左->右->根，所以创建完根以后，应该先创建右子树，再创建左子树，这与前面那题是有区别的
root.right = buildTreeChild(postorder, inorder, rootIndex + 1, inEnd);
root.left = buildTreeChild(postorder, inorder, inBegin, rootIndex - 1);
return root;
}
private int findVal(int[] inorder, int inBegin, int inEnd, int val) {
for (int i = inBegin; i <= inEnd; i++) {
if (inorder[i] == val) {
return i;
}
}
return -1;
}
}
12. 二叉树创建字符串
题目链接：606. 根据二叉树创建字符串
解题思路：
- 先把题读懂，括号外面的表示根，第一个括号里的表示左子树，第二个括号里的表示右子树，括号里进行递归嵌套
- 值得注意的是，当左子树为空，右子树为空时，这时的两个括号都可以省略；当左子树不为空，右子树为空时，这时的右子树括号可以省略；当左子树为空，右子树不为空时，左子树的括号不能省略！这里需要特别注意。写代码时要注意分类讨论的条理性和严谨性
- 利用StringBuffer或者StringBuilder创建变量，用append方法进行字符的拼接
代码如下：
class Solution {
public StringBuffer stringBuffer = new StringBuffer();
public String tree2str(TreeNode root) {
tree2strChild(root);
return stringBuffer.toString();
}
private void tree2strChild(TreeNode root) {
if(root == null) {
return;
}
stringBuffer.append(root.val);
if(root.left != null) {
stringBuffer.append("(");
tree2strChild(root.left);
stringBuffer.append(")");
}else {
if(root.right == null) {
return;
}else {
stringBuffer.append("()");
}
}
if(root.right != null) {
stringBuffer.append("(");
tree2strChild(root.right);
stringBuffer.append(")");
}else {
return;
}
}
}
13. 二叉树前序非递归遍历实现
题目链接：144. 二叉树的前序遍历
解题思路：
- 先需要利用到树中底层的节点，后用到上层的节点，所以这道题需要利用到栈
- 先不断向左遍历，同时将根节点放入栈和“数组”中，直至为null
- 再将栈顶元素出栈，并记录下来，开始遍历它的右子树
- 重复2和3，直至遍历完整棵树，且栈为空
代码如下：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
if(root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
list.add(cur.val);
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
}
return list;
}
}
14. 二叉树中序非递归遍历实现
题目链接：94. 二叉树的中序遍历
解题思路大致与二叉树前序非递归遍历实现相同，故不再赘述
代码如下：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
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();
list.add(top.val);
cur = top.right;
}
return list;
}
}
15. 二叉树后序非递归遍历实现
题目链接：145. 二叉树的后序遍历
我们可以先试着按照前面前序和中序的非递归仿写后序的非递归遍历实现
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
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();
if(top.right == null) {
list.add(top.val);
}else {
cur = top.right;
}
}
return list;
}
}
但是这个代码是存在问题的，因为根节点是最后遍历的，在通过弹出栈顶元素来找到右节点后，后续就可能找不到根节点了，因此我们可以先peek一下，有必要时再弹出栈顶元素
修改后的代码：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
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.peek();
if(top.right == null) {
stack.pop();
list.add(top.val);
}else {
cur = top.right;
}
}
return list;
}
}
到这就完了吗？NoNoNo…我们试着举一个例子来验证一下这个代码的可行性
仔细分析，不难发现，代码会在节点1和节点4之间陷入死循环，这时，我们就需要用一个变量来标记4这个节点，使得当遍历节点4后，遍历节点2时，不会进入else语句（后续再次遍历节点4），而是进入if语句（将节点2弹出），这样就不会陷入死循环了，代码到此也就完善了！
完善后的代码：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
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) {
stack.pop();
list.add(top.val);
prev = top;
}else {
cur = top.right;
}
}
return list;
}
}
