Java-数据结构-二叉树习题(2)

第一题、平衡二叉树

① 暴力求解法

📚 思路提示：

该题要求我们判断给定的二叉树是否为"平衡二叉树"。

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

也就是说需要我们会求二叉树的高，并且要对节点内所有左右子树进行"高度差是否>1"的判断~

那么首先我们先回顾一下如何求一个二叉树的高：

首先，初始高度为0，然后仍然还是通过我们最常用的"将树不断分解成两个子树"，通过不断地分解子树，达到树的最底层开始往回递归，每递归一次就使得高度++，最终返回两个子树的高的最大值，即可求得该树的高度。

该过程在之前模拟实现二叉树时就已经讲解过，所以这里就不再过多赘述了~

    // 获取二叉树的高度public int TreeHeight(TreeNode root) {if(root == null){return 0;}int leftHeight = TreeHeight(root.left);int rightHeight = TreeHeight(root.right);return Math.max(leftHeight,rightHeight) + 1;}

那此时我们既然已经学会了求二叉树的高度，我们用最简单的思想解决该题："求出每一个结点的左右树高度，并判断该树是否为平衡二叉树，若是则向上返回true，否不是则向上返回false"

需要注意的是：当我们将根节点传给 isBalanced() 函数时，我们得到的是" 根节点左右子树的高度差 "，通过根节点左右子树的高度差，我们就能够知道" 该根节点的树平衡 "，但是平衡二叉树的要求是" 所有结点都应是平衡树 "，所以仅仅判断传入结点是否平衡，是不够的，还要求它左右子树本身也要是平衡的(递归回来就会不断进行判断，只要中途出现了非平衡，就会递归回根节点) 

⭐ 图示：

📚 首先调用 isBalanced 函数，对于根节点 3：

📕 先计算 TreeHeight(9) 和 TreeHeight(20) 并比较它们的差的绝对值是否小于等于 1 。

📕 然后我调用 isBalanced(9) 来检查以 9 为根节点的子树是否平衡(return true)

📕 然后调用 isBalanced(20) 来检查以 20 为根节点的子树是否平衡(return true)

(对于 isBalanced(20) 需要我们进一步调用 isBalanced(15) 和  isBalanced(7) 检查它们是否平衡，这里无论树有多长，都是一样的步骤，就不过多赘述了)

📖 代码示例：

class Solution {public boolean isBalanced(TreeNode root){if(root == null){return true;}int leftLen = TreeHeight(root.left);int rightLen = TreeHeight(root.right);return Math.abs(leftLen - rightLen) <= 1 && isBalanced(root.left) && isBalanced(root.right);}public int TreeHeight(TreeNode root) {if(root == null){return 0;}int leftHeight = TreeHeight(root.left) + 1;int rightHeight = TreeHeight(root.right) + 1;return Math.max(leftHeight,rightHeight);}
}

以上解题方法的时间复杂度为O(n^2)，因为做了很多多余的计算(对一棵树进行多次求高)

② 自底向上递归法

📚 思路提示：

上述方法我们每判断一棵树，就都同时对它求了高度，但是因此就会出现很多重复遍历某个结点的情况，所以我们就想到了这个优化的方法：

自底向上的递归，求高度的同时，也对子树是否平衡进行判断，这样的方法时间复杂度为O(n)

具体的思路与第一种解法大同小异，只是该换了一种思路，将求高度与平衡判断放到了一起，这里就不过多赘述了，我们直接看代码~

📖 代码示例：

class Solution {public boolean isBalanced(TreeNode root) {return checkBalance(root)!= -1;}private int checkBalance(TreeNode root) {if (root == null) {return 0;}int leftHeight = checkBalance(root.left);if (leftHeight == -1) {return -1;}int rightHeight = checkBalance(root.right);if (rightHeight == -1) {return -1;}if (Math.abs(leftHeight - rightHeight) > 1) {return -1;}return Math.max(leftHeight, rightHeight) + 1;}
}

第二题、对称二叉树

📚 思路提示：

该题要求我们判断一个二叉树是否对称，一个树对称就需要有以下的要求：

📕 一个树对称，就要求它的左右子树都对称

📕 如果一个树对称，那么它的" 左侧子树的左子树 "等于" 对应右侧子树的右子树 "

同样的，它的" 左侧子树的右子树 "也等于" 对应右侧子树的左子树 "

⭐ 图示：

📖 代码示例：

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

第三题、二叉树遍历

📚 思路提示：

该题要求我们按照它给出的字符串，通过前序遍历的顺序创建一个二叉树，并且再使用中序遍历打印出二叉树

相信大家现在对二叉树的遍历已经十分熟悉了，那么这题对大家来说就并没有难度~

我们只需要通过递归的方式来创建二叉树，再用递归的方式去遍历创建好的二叉树并打印各个结点

⭐ 图示：

📖 代码示例：

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val){this.val = val;}
}
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);String s = in.next();TreeNode root = createTree(s);display(root);}public static int i = 0;public static TreeNode createTree(String s){char a = s.charAt(i++);if(a == '#'){return null;}TreeNode root = new TreeNode(a);root.left = createTree(s);root.right = createTree(s);return root;}public static void display(TreeNode root){if(root == null){return;}display(root.left);System.out.print(root.val + " ");display(root.right);}
}

第四题、二叉树的层序遍历

📚 思路提示：

该题要求我们通过题中给定的二叉树根节点，对二叉树进行层序遍历

想要实现二叉树的层序遍历，我们就要创建一个"辅助队列"：

📕 用于存储该层的结点值到List中

📕 用于存储下一层的结点

我们需要做的就是创建一个while()循环，当队列不为空时，循环就继续进行，而在循环内：

📕 首先，将队列中原有结点(即上一层的结点)的值存入临时的ArrayList中

📕 然后，通过队列中原有结点，找出下一层的结点，将非空结点存入队列，便于下次访问

📕 最后，在这次循环的末尾，将临时的ArrayList存入List中

⭐ 图示：

📖 代码示例：

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list = new ArrayList<List<Integer>>();Deque<TreeNode> deque = new ArrayDeque<>();if (root == null) {return list;}deque.push(root);while (!deque.isEmpty()) {List<Integer> liSt = new ArrayList<>();int len = deque.size();for (int i = 0; i < len; i++) {TreeNode node = deque.removeLast();if (node != null) {liSt.add(node.val);if(node.left != null){deque.push(node.left);}if(node.right != null){deque.push(node.right);}}}list.add(liSt);}return list;}
}

第五题、二叉树的层序遍历 II

📚 思路提示：

这题和上一题其实都可以归结于一道题，它们的区别就是将数据的存储从第一层到最后一层，改成了从最后一层到第一层。

其实想要实现这个并不需要我们逆序遍历或者逆序存储之类的，我们只需要稍微改换一下每一次临时ArrayList的存储位置即可：

⭐ 图示：

📖 代码示例：

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> list = new ArrayList<List<Integer>>();Deque<TreeNode> deque = new ArrayDeque<>();if (root == null) {return list;}deque.push(root);while (!deque.isEmpty()) {List<Integer> liSt = new ArrayList<>();int len = deque.size();for (int i = 0; i < len; i++) {TreeNode node = deque.removeLast();if (node != null) {liSt.add(node.val);if(node.left != null){deque.push(node.left);}if(node.right != null){deque.push(node.right);}}}list.add(0,liSt);}return list;}
}

第六题、二叉树的最近公共祖先

📚 思路提示：

想要求出一棵树中两个节点的最近公共祖先，就要先知道什么是公共祖先：

还是一样的，通过递归的方法，不断地向下探索，直到找到p或者q的时候，就开始向上递归，当然遇到null的时候也要开始向上递归~而我们需要搜索的值有两个，但只要遇到其中之一我们就要递归，所以在查找公共祖先的过程中，我们需要关注以下几点：

📕 如果在递归的过程中，root的左右子结点一个为空一个不为空，则代表不为空的一边找到了目标值，返回不为空的那一边的结点
(有可能是此时另一个要找的结点在根节点的右子树中)
(有可能是此时另一个要找的结点在已找到的结点的子树中)
(包含了这两种情况，并且都能妥善的解决)

📕 如果root的左右子节点均不为空，则代表此时已经找到了两个节点的最近公共祖先，直接返回root即可

📕 以上方法已经包含了(左右子节点均为空)的解决方法，若中途出现该情况，则最后的root返回值会是null

⭐ 图示：

📖 代码示例：

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

那么这次关于二叉树的习题相关知识，就为大家分享到这里啦，作者能力有限，如果有讲得不清晰或者不正确的地方，还请大家在评论区多多指出，我也会虚心学习的！那我们下次再见哦