当前位置：首页 > news >正文

Java-数据结构-二叉树-习题(二) (´▽`)ﾉ

news 来源：原创 2024/9/20 11:46:18

文本目录：

❄️一、习题一(分层遍历)：

▶ 思路：

▶ 代码：

❄️二、习题二(二叉树的最近公共祖先)：

▶ 思路：

▶ 代码：

❄️三、习题三(从前序和中序遍历序列中构造二叉树)：

▶ 思路：

▶ 代码：

❄️四、习题四(从中序和后序遍历序列中构造二叉树)：

▶ 思路：

▶ 代码：

❄️五、习题五(根据二叉树创建字符串)：

▶ 思路：

▶ 代码：

❄️六、总结：

❄️一、习题一(分层遍历)：

☞ 题的链接：

二叉树的层次遍历

▶ 思路：

我们的这个题呢和我们在二叉树的基础那个博客的那个中的层序遍历是差不多的。我们返回的是 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 和 qTreeNode 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，代码到这里就结束了，我们这道题也就结束了。