Java-数据结构-二叉树-习题(二) (´▽`)ﾉ
文本目录：
❄️一、习题一(分层遍历)：
☞ 题的链接：
▶ 思路：
我们的这个题呢和我们在 二叉树的基础那个博客的那个中的层序遍历 是差不多的。我们返回的是 List<List<TreeNode>> 这样的返回类型，我们呢要把每一层的节点放入到 List 当中之后我们在把 List 放入到 List<List<TreeNode>> 当中。
对于这个题呢，我们要把我们每次入完队的长度计算出来，之后我们出队，并且要把出队的节点的val 放入到 List 当中，直到我们这一层的队列的长度为 0 是就结束，进行下次层的遍历。我们来看看图：
▶ 代码：
Ok，我们来看看代码如何编写，是怎样在 层序遍历上进行改变的：
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();
List<Integer> lsit = new LinkedList<>();
while (size != 0) {
TreeNode cur = queue.poll();
lsit.add(cur.val);
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
size--;
}
ret.add(lsit);
}
return ret;
}❄️二、习题二(二叉树的最近公共祖先)：
☞ 题的链接：
▶ 思路：
这个题呢还是很简单的，只要理解了就非常简单了。我们先来看看什么是最近的公共祖先，就是我们这两个节点的 p q 的最近的公共节点，我们来看看什么样的：
这种呢就是我们的公共祖先，我们再来看看都有哪些情况对于公共祖先： 
就有这四种情况，当然了我们的 p 和 q 是可以进行交换的。我们来看看它们的条件是什么：
这里要注意的是，我们寻找的是p 和q 的节点，当我们的没有找到的时候呢，我们会返回null
OK，这呢就是这些情况出现的条件了，我们还需要去遍历我们的左子树和右子树找节点。
▶ 代码：
我们来看看我们这题的代码的编写：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
//第一种情况
if (root == p || root == q) {
return root;
}
//找节点 p 和 q
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 leftTree;
}else {
return rightTree;
}
} ❄️三、习题三(从前序和中序遍历序列中构造二叉树)：
☞ 题的链接：
▶ 思路：
我们知道对于 前序遍历是：根 左 右 。中序遍历是：左 根 右。我们呢就是在前序遍历中寻找根节点，之后用这个根节点在中序中找到这个根节点，这样根节点的左面的数据为左子树，右面的数据为右子树。我们要在中序遍历中要记录中序遍历的开头和结尾，每次的树的创建我们都需要用到，根节点，开头的节点，结尾的节点，这三个节点配合着去创建树，我们这样说呢，不是很直观，我们画个图来分析一下是如何实现的：
这个呢就是我们的这个题的思路， 但是在这里呢我们有一个非常隐蔽的问题，我们来看：
我们也要记住在设置 左子树 和 右子树 时的 开始位置 和 结束位置 要重新计算，
在设置左子树的时候 开始位置不变，结束为止为 根节点 - 1，
在设置右子树的时候 结束为止不变，开始位置为 根节点 + 1。
所以我们这里要特别注意一下。那么我们接下来看看代码如何编写：
▶ 代码：
class Solution {
public int preorderIndex;//这个就是 i 这个下标
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder,inorder,0,inorder.length - 1);
}
public TreeNode buildTreeChild(int[] preorder,int[] inorder,int ib,int ie) {
//结束条件
if (ib > ie) {
return null;
}
//设置先序遍历的根节点
TreeNode root = new TreeNode(preorder[preorderIndex]);
//找我们先序遍历的 i 下标这个节点在 中序遍历的位置
int rootindex = findval(inorder,ib,ie,preorder[preorderIndex]);
//找完之后我们要把 i 下标增加一位
preorderIndex++;
//递归设置左子树的节点
root.left = buildTreeChild(preorder,inorder,ib,rootindex - 1);
//递归设置右子树的节点
root.right = buildTreeChild(preorder,inorder,rootindex + 1,ie);
return root;
}
public int findval(int[] inorder,int ib,int ie,int val){
for (int i = ib; i <= ie; i++) {
if (inorder[i] == val) {
return i;
}
}
return -1;
}
}Ok啊，这个题呢就结束了，我们在来看看下一个题。
❄️四、习题四(从中序和后序遍历序列中构造二叉树)：
☞ 题的链接：
▶ 思路：
当我们理解我们上面的 从先序和中序遍历创建二叉树 的话呢，那么我们在做这道题的时候呢就非常的容易了，我们的 中序遍历：左 根 右 后序遍历：左 右 根。
我们在这里利用 后序遍历来找根节点，就是我们 后序遍历的最后一个节点，之后我们从后往前走，就是变成 先创建右子树 再创建左子树。
因为思路是差不多的，所以我们直接来看看代码是如何编写的：
▶ 代码：
class Solution {
public int postorderInder;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postorderInder = postorder.length - 1;// 最后一个数据的下标
return buildTreeChild(inorder, postorder, 0, inorder.length - 1);
}
public TreeNode buildTreeChild(int[] inorder, int[] postorder, int ib, int ie) {
if (ib > ie) {
return null;
}
TreeNode root = new TreeNode(postorder[postorderInder]);
int rootIndex = findval(inorder, postorder[postorderInder], ib, ie);
postorderInder--;
root.right = buildTreeChild(inorder, postorder, rootIndex + 1, ie);
root.left = buildTreeChild(inorder, postorder, ib, rootIndex - 1);
return root;
}
public int findval(int[] inorder, int val, int ib, int ie) {
for (int i = ib; i <= ie; i++) {
if (inorder[i] == val) {
return i;
}
}
return -1;
}
}OK，我们的这道题也到这里就结束了，我们来看看这篇博客的最后一道题了。
❄️五、习题五(根据二叉树创建字符串)：
☞ 题的链接：
▶ 思路：
我们这个题呢，我们开始直接放入我们根的节点，之后当我们来看左子树如何操作：
左子树不为空 的时候我们先添加一个 '(' 之后我们添加数据，添加之后我们再添加 ')' ，
左子树为空 的话，我们还要判断一下其右子树为不为空，如果为空就直接退出，不为空就直接 添加 '()'
右子树如何操作：
右子树不为空的话 我们还是执行先添加一个 '(' 之后添加数据，之后是 ')'
右子树为空的话 我们直接退出就可以了，因为这里我们已经判断完了左子树，左子树为空，我们才退出的判断左子树，才能判断右子树，所以这里我们为空时，直接退出就可以了。
这里注意我们的字符串使用 StringBuilder 来进行字符串的连接。
我们来看看图，更加直观的了解一下：
我们再来看看另一种情况：
我们按照这个思路进行编写代码就可以了，我们来看看如何进行编写的：
▶ 代码：
public String tree2str(TreeNode root) {
if (root == null) {
return null;
}
//StringBuilder是可以把字符串连接起来的
StringBuilder stringBuilder = new StringBuilder();
tree2strChild(root, stringBuilder);
return stringBuilder.toString();
}
public void tree2strChild(TreeNode root, StringBuilder stringBuilder) {
if (root == null) {
return;
}
//对于根节点我们直接放入
stringBuilder.append(root.val);
if (root.left != null) {
stringBuilder.append('(');
tree2strChild(root.left, stringBuilder);
stringBuilder.append(')');
} else {
if (root.right == null) {
return;
} else {
stringBuilder.append("()");
}
}
if (root.right != null) {
stringBuilder.append('(');
tree2strChild(root.right, stringBuilder);
stringBuilder.append(')');
} else {
return;
}
}OK，代码到这里就结束了，我们这道题也就结束了。
❄️六、总结：
OK啦，今天的练习题呢就到这里就结束了，还是那句话，对于二叉树的题，我们要时刻记住递归的性质与应用。今天的题呢还是比较难理解的，我们一定要配合着画图去理解。 让我们期待下一篇博吧！！！拜拜~~~
原文地址：https://blog.csdn.net/2303_80388948/article/details/142217099
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！