Java-数据结构-二叉树习题(3)
第一题、从前序与中序遍历序列构造二叉树
📚 思路提示：
该题要求我们通过一个二叉树的前序遍历与中序遍历的结果，来构造出该二叉树并且返回根节点。
而想要通过前序遍历与中序遍历来得到这个二叉树，首先我们得知道通过前序遍历与中序遍历的数组，我们能知道关于这个二叉树的何种关系，比如：二叉树的根节点是否能找到，是否能知道二叉树的左右子树是哪一部分...等等。
📕 通过前序遍历数组，我们能够找到该二叉树的根节点(前序遍历数组的第一位)
📕 通过中序遍历数组，我们能通过树的根节点，找到它两侧子树的所有结点
有了这两个关键信息，我们就能够通过不断递归子树的方式，不断缩小根节点左右两侧子树结点的范围，最终将其确定，并向上递归拼接成二叉树~
具体的思路是，先确定根节点的位置，然后在中序遍历数组中找到根节点的位置index，则根节点的左子树结点范围[0,index - 1]，根节点的右子树节点范围[index + 1,len]。
然后开始将左子树结点递归，查找左子树的左部分与右部分，最后当范围不合法(left > right)时，开始向上递归。
⭐ 图示：
📖 代码示例：
class Solution {
public int start = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return bulidTreeChild(preorder,inorder,0,inorder.length - 1);
}
public TreeNode bulidTreeChild(int[] preorder,int[] inorder,int begin,int end){
if(begin > end){
return null;
}
int num = preorder[start];
TreeNode root = new TreeNode(num);
start++;
int index = findNode(inorder,num,begin,end);
root.left = bulidTreeChild(preorder,inorder,begin,index - 1);
root.right = bulidTreeChild(preorder,inorder,index + 1,end);
return root;
}
public int findNode(int[] inorder,int key,int begin,int end){
for(int i = begin;i <= end;i++){
if(inorder[i] == key){
return i;
}
}
return -1;
}
}第二题、从中序与后序遍历序列构造二叉树
📚 思路提示：
和上一题基本上是一致的思路，仍旧是通过两种遍历数组，找到能够获得的条件，再通过这种条件不断递归，直到范围不合法(即此树分支无更多元素)就开始返回，最终分支递归相连，构造出二叉树
📕 通过后序遍历数组，我们能够找到根节点(数组的最后一位)
📕 通过中序遍历数组，我们能够找到各个结点的左右两侧二叉树结点(和第一题是一样的)
通过这两点信息，我们就能轻松解决此题啦~主要的思路和第一题是一样的，最主要的是通过中序遍历数组去将树进行分支递归，而另一个数组给的是前序遍历数组还是后序遍历数组，只能代表我们是从前遍历数组还是从后遍历数组而已。
(就不画图啦，和第一个基本一致的，这里不过多赘述)
📖 代码示例：
class Solution {
public int start = 0;
public TreeNode buildTree(int[] inorder, int[] postorder) {
start = postorder.length - 1;
return buildTreeChild(inorder,postorder,0,postorder.length - 1);
}
public TreeNode buildTreeChild(int[] inorder,int[] postorder,int begin,int end){
if(begin > end){
return null;
}
int num = postorder[start];
TreeNode root = new TreeNode(num);
start--;
int index = findTreeNode(inorder,begin,end,num);
root.right = buildTreeChild(inorder,postorder,index + 1,end);
root.left = buildTreeChild(inorder,postorder,begin,index - 1);
return root;
}
public int findTreeNode(int[] inorder,int begin,int end,int key){
for(int i = begin;i <= end;i++){
if(inorder[i] == key){
return i;
}
}
return -1;
}
}第三题、根据二叉树创建字符串
① 前序遍历解法
📚 思路提示：
这题需要我们将二叉树转换成一个用()构成左右树关系的字符串，这里面需要注意的细节并不少，想要解决这题，我们需要先分解一下各种情况(指left == null ，right != null等)，看看各种情况都是如何解决的。
我们按照题中给的两个测试用例来进行分析：
📌 示例1：
我们可以看到，测试用例给出的二叉树如果不忽略null，那么我们得到的二叉树字符串其实应该是这样的： "1(2(4)( ) )(3( )( ) )"，而化简后得到的是这样的："1(2(4) )(3)"，这我们可以看出：
📕 当根节点的right为null时，该( )就可以被省略
📕 当根节点的right或left不为null时，我们需要将left或right左右都加上()
而通过这个字符串，我们还能够看出结构大概为："root(root.left(..)(..))(root.right(..)(..))" 所以：
📕 当root.left或者root.right不为null时，我们需要先处理好root.left/right，再将括号闭合(递归)
📌 示例2：
示例2中有非常重要的一点需要我们注意，观察输出的字符串中有一个"()"：
📕 当root.left为null，但root.right不为null时，"()"不能够忽略
📖 代码示例：
class Solution {
StringBuilder sb = new StringBuilder();
public String tree2str(TreeNode root) {
tree2Str(root);
return sb.toString();
}
public void tree2Str(TreeNode root){
if(root == null){
return;
}
sb.append(root.val);
if(root.left != null){
sb.append("(");
tree2Str(root.left);
sb.append(")");
}else {
if(root.right == null){
return;
}else {
sb.append("()");
}
}
if(root.right != null){
sb.append("(");
tree2Str(root.right);
sb.append(")");
}else {
return ;
}
}
}② 后序遍历解法
📚 思路提示：
而此题采用后续遍历的解法将更为简单，因为前序遍历，我们需要考虑各种因素，比如当前结点的left是否为null，而当前结点的left如果为null，那么right又是否为空，而left如果不是null又...等等特别繁琐的思路。
而后续遍历，则代表我们通过递归的方式，直接先拿到树的最下面的结点，然后直接取得该结点的值，return给上一个结点的(left/right)，然后通过对这个结点的left和right进行判断，很容易就能从内部往外构造出一个字符串：
我们通过两个测试用例的部分分支来进行证明：
⭐ 图示：
📖 代码示例：
class Solution {
public String tree2str(TreeNode root) {
if (root == null) {
return null;
}
String left = tree2str(root.left);
String right = tree2str(root.right);
if (left == null && right == null) {
return String.valueOf(root.val);
}
if (right == null) {
return root.val + "(" + left + ")";
}
if (left == null) {
return root.val + "()(" + right + ")";
}
return root.val + "(" + left + ")" + "(" + right + ")";
}
}第四题、二叉树的前序遍历
做了那么多不太好解决的题，总该来点简单的给自己点信心对吧~
📚 思路提示：
很简单很简单啦~题目要求的是让我们通过前序遍历的顺序将二叉树的结点val都存入一个List<Integer>中，然后返回这个List~
那么我们只需要创建一个List<Integer>，用ArrayList去实现它。
然后再创建一个方法，采取(先赋值,再走left,再走right)的步骤(前序遍历)，通过不断递归调用该方法，并且将遍历到的非null的值添加给List，最后List中的值的顺序就是我们的前序遍历了
📖 代码示例：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> cur = new ArrayList<>();
preOrder(root,cur);
return cur;
}
public void preOrder(TreeNode root,List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val);
preOrder(root.left,res);
preOrder(root.right,res);
}
}第五题、二叉树的中序遍历
📚 思路提示：
思路和上一题的思路是一模一样的，只需要该换一下方法中的遍历方式(递归root.left,赋值,递归root.right)，即可
📖 代码示例：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> cur = new ArrayList<Integer>();
inOrder(root,cur);
return cur;
}
public void inOrder(TreeNode root,List<Integer> cur) {
if (root == null) {
return;
}
inOrder(root.left,cur);
cur.add(root.val);
inOrder(root.right,cur);
}
}第六题、二叉树的后序遍历
📚 思路提示：
不多赘述啦~和上面都是一样的，来点简单的换换口味嘛~
📖 代码示例：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> cur = new ArrayList<Integer>();
postOrder(root,cur);
return cur;
}
public void postOrder(TreeNode root,List<Integer> res) {
if(root == null){
return;
}
postOrder(root.left,res);
postOrder(root.right,res);
res.add(root.val);
}
}那么这次关于二叉树的习题相关知识，就为大家分享到这里啦，作者能力有限，如果有讲得不清晰或者不正确的地方，还请大家在评论区多多指出，我也会虚心学习的！那我们下次再见哦