• 11.24总结二叉树

    目录

    一.将二叉搜索树变成有序链表

    二.从前序遍历和中序遍历构建二叉树

    三.从中序遍历和后续遍历创建字符串

    四.二叉树创立字符串

    五.订正题目

    六.排序子序列

    七.二叉树非递归遍历

    1.前序遍历

    3.后续遍历

    一.将二叉搜索树变成有序链表

    我们的思路就是因为一颗二叉搜索树所以中序遍历是有序的,从小到大 排的.

    所以我们的思路就是一边遍历一边修改节点指向.因为是双向链表,就把left和right修改指向

    所以再需要打印那一步我们开始搞事情,我们需要对他修改指向,根据上图所示,我们最好就是

    left改为下一个的.right改为上一个的.

    我们就从第一个走到根节点这一步开始思考

    如果是第一个那么就是左子树最左边的树,那么他的下一个就是null.上一个就是他的根节点.

    然后回推到他的下一个,他的下一个就是刚刚那个节点,上一个就是他的右子树.

    所以我们需要有一颗后继节点.记录上一个节点的位置.

    并且这个节点得是成员变量.不然每次递归,他都会重置

    这里我们发现,root指向了prev.但是prev并没有连接到root.其实prev的right就是root啊

    所以我们需要在他移向root之前让他指向cur;

    根据如此递归,递归完成的时候,就变成了双向链表,就到最后一个节点的时候,因为prev还是和他连接的,他的左节点连接的是prev.他的右节点本来就是null.所以没毛病

    那就回到了主函数,

    我们现在虽然得到的是主函数,但是root还是指向的是左节点,我们需要一个头结点

    就开始迭代找.或者定义一个头结点,当prev为null的时候满足

    1. 方法一：非递归版
    2. 解题思路：
    3. 1.核心是中序遍历的非递归算法。
    4. 2.修改当前遍历节点与前一遍历节点的指针指向。
    5.     import java.util.Stack;
    6.     public TreeNode ConvertBSTToBiList(TreeNode root) {
    7.     if(root==null)
    8.     return null;
    9.     Stack stack = new Stack();
    10.     TreeNode p = root;
    11.     TreeNode pre = null;// 用于保存中序遍历序列的上一节点
    12.     boolean isFirst = true;
    13.     while(p!=null||!stack.isEmpty()){
    14.     while(p!=null){
    15.     stack.push(p);
    16.     p = p.left;
    17.     }
    18.     p = stack.pop();
    19.     if(isFirst){
    20.     root = p;// 将中序遍历序列中的第一个节点记为root
    21.     pre = root;
    22.     isFirst = false;
    23.     }else{
    24.     pre.right = p;
    25.     p.left = pre;
    26.     pre = p;
    27.     }
    28.     p = p.right;
    29.     }
    30.     return root;
    31.     }
    32. 方法二：递归版
    33. 解题思路：
    34. 1.将左子树构造成双链表，并返回链表头节点。
    35. 2.定位至左子树双链表最后一个节点。
    36. 3.如果左子树链表不为空的话，将当前root追加到左子树链表。
    37. 4.将右子树构造成双链表，并返回链表头节点。
    38. 5.如果右子树链表不为空的话，将该链表追加到root节点之后。
    39. 6.根据左子树链表是否为空确定返回的节点。
    40.     public TreeNode Convert(TreeNode root) {
    41.     if(root==null)
    42.     return null;
    43.     if(root.left==null&&root.right==null)
    44.     return root;
    45.     // 1.将左子树构造成双链表，并返回链表头节点
    46.     TreeNode left = Convert(root.left);
    47.     TreeNode p = left;
    48.     // 2.定位至左子树双链表最后一个节点
    49.     while(p!=null&&p.right!=null){
    50.     p = p.right;
    51.     }
    52.     // 3.如果左子树链表不为空的话，将当前root追加到左子树链表
    53.     if(left!=null){
    54.     p.right = root;
    55.     root.left = p;
    56.     }
    57.     // 4.将右子树构造成双链表，并返回链表头节点
    58.     TreeNode right = Convert(root.right);
    59.     // 5.如果右子树链表不为空的话，将该链表追加到root节点之后
    60.     if(right!=null){
    61.     right.left = root;
    62.     root.right = right;
    63.     }
    64. return left!=null?left:root;        
    65.     }
    66. 方法三：改进递归版
    67. 解题思路：
    68. 思路与方法二中的递归版一致，仅对第2点中的定位作了修改，新增一个全局变量记录左子树的最后一个节点。
    69.     // 记录子树链表的最后一个节点，终结点只可能为只含左子树的非叶节点与叶节点
    70.     protected TreeNode leftLast = null;
    71.     public TreeNode Convert(TreeNode root) {
    72.     if(root==null)
    73.     return null;
    74.     if(root.left==null&&root.right==null){
    75.     leftLast = root;// 最后的一个节点可能为最右侧的叶节点
    76.     return root;
    77.     }
    78.     // 1.将左子树构造成双链表，并返回链表头节点
    79.     TreeNode left = Convert(root.left);
    80.     // 3.如果左子树链表不为空的话，将当前root追加到左子树链表
    81.     if(left!=null){
    82.     leftLast.right = root;
    83.     root.left = leftLast;
    84.     }
    85.     leftLast = root;// 当根节点只含左子树时，则该根节点为最后一个节点
    86.     // 4.将右子树构造成双链表，并返回链表头节点
    87.     TreeNode right = Convert(root.right);
    88.     // 5.如果右子树链表不为空的话，将该链表追加到root节点之后
    89.     if(right!=null){
    90.     right.left = root;
    91.     root.right = right;
    92.     }
    93. return left!=null?left:root;        
    94.     }

    二.从前序遍历和中序遍历构建二叉树

    因为前序遍历是先根遍历,可以通过前序找到根节点,然后在中序遍历这里找到左子树和右子树

    再再左子树和右子树分别找前序遍历的根,如此递归,

    但是会发现,每次递归左子树和右子树对应的数组会变小,这里我认为也不需要分隔数组,就只要改变数组指向就好

    第一步,在前序数组开始遍历,没遍历一个元素,就去中序遍历循环找对应的元素下标

    第二步开始分隔中序数组,左边的是左子树右边的是右子树,

    定义两个指针来指向左子树和右子树开头和结尾.

    我这里用迭代的方式做,出现了问题一组循环,多组加,就导致可能数组越界

    所以应该还是得试试递归的方式

    因为考虑到题干中给的函数只有两个数组变量.所以我们另外再建立一个方法,添加指针变量

    这里我没有考虑完全.如果是到了空节点,就直接递归回去了.就不需要在前序数组再往前一位,

    要先判断

    我这里出现了一个及其离谱的错误,左右树创建的时候写反了

    这里的思路就是先判断左指针是否大于右指针.

    因为每次递归都会找每颗子树自己的根.就会导致指针越来越接近

    直到小于或者大于,就说明

    已经递归到自身已经不能再往下了,就说明到了null了,所以要给递归弄一个结束条件,也就是这个条件

    然后创建每次递归找到的根节点,就以前序遍历为主

    再从中序遍历找到对应的下标,把中序数组以下标为界限左右各分为左子树右子树,

    再对这次递归的节点的左节点和右节点分别来创建再次进行递归

    因为这次递归的节点的左子树的节点又是一个新的根节点,所以就缩小范围按之前数组的界限

    就好

    1. class Solution {
    2.     public int findIndex(int[] inorder,int key,int ib,int ie){
    3.         for(int i=ib;i<=ie;i++){
    4.             if(inorder[i]==key){
    5.                 return i;
    6.             }
    7.         }
    8.         return -1;
    9.  
    10.  
    11.     }
    12.     public int preIndex=0;//防止每次递归都会变
    13.     public TreeNode buildTree(int[] preorder, int[] inorder) {
    14.         if(preorder==null||inorder==null) return null;
    15.         return  createTree(preorder,inorder,0,inorder.length-1);
    16.     }
    17.     public TreeNode createTree(int[] preorder,int[] inorder,int inbegin,int inend){
    18.         if(inbegin>inend){
    19.             return null;
    20.         }
    21.         //满足这个条件说明没有左树或者右树了
    22.         TreeNode root=new TreeNode(preorder[preIndex]);
    23.         int index=findIndex(inorder,preorder[preIndex],inbegin,inend);//找到根在中序遍历的位置
    24.         if(index==-1) return null;
    25.         preIndex++;
    26.         //递归在各自的左树右树找相应的根节点
    27.         root.left=createTree(preorder,inorder,inbegin,index-1);
    28.         root.right=createTree(preorder,inorder,index+1,inend);
    29.         return root;
    30.  
    31.     }
    32. }

    三.从中序遍历和后续遍历创建字符串

    原理跟上题一样,唯一要改变的就是从后往前遍历,

    这里发现因为要从后往前遍历,就要把遍历的指针初始为前序数组末尾,

    但是不能放在外面因为数组定义在方法外

    这里我们的处理方法,就是还是在外面初始化,然后再函数内设为数组末尾就好了

    但是还是要注意.因为后续遍历,是左右根.如果从后往前看,就是根右子树,左子树,所以应该是先建立右子树再建立左子树.

    1. class Solution {
    2.      int preIndex=0;
    3.     public TreeNode buildTree(int[] inorder, int[] postorder) {
    4.         if(inorder==null||postorder==null) return null;
    5.          preIndex=postorder.length-1;
    6.         return createTree(inorder,postorder,0,inorder.length-1); 
    7.  
    8.     }
    9.     public TreeNode createTree(int[]inorder,int[]postorder,int ib,int ie){
    10.         if(ib>ie) return null;
    11.  
    12.         TreeNode root=new TreeNode(postorder[preIndex]);
    13.         int index=findIndex(inorder,ib,ie,postorder[preIndex]);
    14.         if(index==-1) return null;
    15.         preIndex--;
    16.         root.right=createTree(inorder,postorder,index+1,ie);
    17.         root.left=createTree(inorder,postorder,ib,index-1);
    18.         return root;
    19.  
    20.     }
    21.     public int findIndex(int[] inorder,int ib,int ie,int key){
    22.         for(int i =ib;i<=ie;i++){
    23.             if(inorder[i]==key){
    24.                 return i;
    25.             }
    26.         }
    27.         return -1;
    28.     }
    29. }

    四.二叉树创立字符串

    这题很简单,从根开始,遇到左子树开始加个左括号,加上左子树的根,再往下遍历,一个根左右子树遍历完加一个括号,再开始遍历右子树

    这里还有一个注意点,如果左子树不是空,但是右子树是空,是不加括号的,

    但是如果左子树是空,右子树不是空就加括号.

    这里我们重新建立一个方法.因为题目要求string.但是这题涉及到拼接,所以我们在另外一个方法用sb拼接完了,再回到函数tostring就可以

    1. class Solution {
    2.     
    3.     public String tree2str(TreeNode root) {
    4.         if(root==null) return null;
    5.         StringBuilder sb=new StringBuilder();//相当于全局变量.不会变
    6.         treetoString(root,sb);
    7.         return sb.toString();
    8.     }
    9.     public void treetoString(TreeNode root,StringBuilder sb){
    10.         if(root==null) return;
    11.         sb.append(root.val);//不管是根节点还是之后的都可以直接加,因为之后的再地柜之前已经加上了括号
    12.  
    13.         if(root.left!=null){
    14.             sb.append('(');
    15.             treetoString(root.left,sb);
    16.             sb.append(')');
    17.         }else{
    18.             if(root.right==null){
    19.                 return;//左节点为空右节点为空的情况不用考虑
    20.             }else{
    21.                 sb.append("()");//左节点为空,右节点为空,根据题意需要加上括号
    22.             }
    23.         }
    24.         if(root.right==null){
    25.             //这种情况就是左节点为null.且右节点也为null的 情况
    26.             return;
    27.         }else{
    28.             //这种情况就是左节点不为null,且右节点也不为null的情况
    29.              sb.append('(');
    30.             treetoString(root.right,sb);
    31.             sb.append(')');
    32.         }

    五.订正题目

    普通方法里不能有静态变量.静态方法也不能有静态变量,静态修饰的属于类变量,

    abstract不能修饰字段

    对成员变量的赋值必须放在方法的内部

    六.排序子序列

    非递增就是 递减但是有连续相同的元素或者只有递减

    所以这道题我们的思路就是先接收

    然后判断,是否一直递减就为一组,有相同的,就继续往后加

    1. import java.util.*;
    2. public class Main{
    3.     public static void main(String[] args){
    4.         Scanner sc=new Scanner(System.in);
    5.         int n=sc.nextInt();
    6.         int[] array=new int[n+1];
    7.         for(int i=0;i
    8.             array[i]=sc.nextInt();
    9.         }//所有数据接收完整开始判断
    10.         int  count=0;
    11.         int i=0;
    12.         while(i//不能用for循环后续会有循环
    13.             if(i1]){
    14.                 while(array[i]<=array[i+1]){
    15.                     i++;
    16.                 }
    17.                 count++;i++;//到另外一组了
    18.             }else if(array[i]==array[i+1]){//每一组开头有可能是相同的
    19.                 i++;
    20.             }else{
    21.                  while(i=array[i+1]){
    22.                     i++;
    23.                 }
    24.                 count++;i++;//到另外一组了
    25.             }
    26.             
    27.         }
    28.         System.out.print(count);
    29.     }
    30. }

    这种情况就算遇到相同的,就把归为下一组了.而我的处理就是也属于这一组.都没有毛病

    七.二叉树非递归遍历

    1.前序遍历

    走到这一步就可能会卡.因为左边遍历完,那么右边怎么办

    所以这里就展现出栈的好处了.可以到最底层的时候,cur就变成了null.就开始往回弹出元素,并打印

    所以 需要再嵌套一个循环

    1. class Solution {
    2.     public List preorderTraversal(TreeNode root) {
    3.         List list=new ArrayList<>();
    4.         Stack stack=new Stack<>();
    5.         TreeNode cur=root;
    6.         while(cur!=null||!stack.isEmpty()){
    7.             while(cur!=null){
    8.                  list.add(cur.val);
    9.                 stack.push(cur);
    10.                 cur=cur.left;
    11.             }
    12.             TreeNode top=stack.pop();
    13.           //  list.add(top.val);
    14.             cur=top.right;
    15.         }
    16.         return list;
    17.     }
    18. }

    但是有一种情况就是如果cur走到底层的右边还是null.就会跳出循环

    所以循环的终止条件应该加一条栈是否为空,如果栈也为空了.就说明真的终止了

    2.中序遍历

    中序遍历根前序类似

    只要更改打印位置即可.让他走到最左边的时候打印.然后栈往回弹的时候分别打印,再判断右是否有,有的话就打印,没有直接往回弹;

    1. class Solution {
    2.     public List inorderTraversal(TreeNode root) {
    3.         List list=new ArrayList<>();
    4.         Stack stack=new Stack<>();
    5.         while(root!=null||!stack.isEmpty()){
    6.             while(root!=null){
    7.                 stack.add(root);
    8.                 root=root.left;
    9.             }
    10.            TreeNode top=stack.pop();
    11.            list.add(top.val);
    12.            if(top.right!=null){
    13.                root=top.right;
    14.            }
    15.         }
    16.         return list;
    17.  
    18.     }
    19. }

    3.后续遍历

    后序比较麻烦,因为如果按之前的改一下打印顺序

    就会在一种情况下进行死循环

    所以我们要判断是否遍历过了.就算右边是空的,但是遍历过了,就直接往后弹了

    就需要建立一个后继节点来记录上次弹的元素

    1. class Solution {
    2.     public List postorderTraversal(TreeNode root) {
    3.         List list=new ArrayList<>();
    4.         Stack stack=new Stack<>();
    5.         TreeNode prev=null;
    6.         while(root!=null||!stack.isEmpty()){
    7.             while(root!=null){
    8.                 stack.push(root);
    9.                 root=root.left;
    10.             }
    11.            TreeNode top=stack.peek();
    12.            if(prev==top.right||top.right==null){
    13.                 stack.pop();
    14.                list.add(top.val);
    15.               prev=top;
    16.            }else{
    17.               root=top.right;
    18.            }
    19.         }
    20.         return list;
    21.  
    22.     }
    23.     
    24. }

    所以每次判断右边的时候如果满足虽然不为空,但是遍历过了.就继继续弹,所以这里就需要一个后继节点,记录弹出的元素.

  • 相关阅读:
    【大数据折腾不息系列】(二) Hadoop 3.0 安装
    支持向量机SVM--线性
    找不到x3daudio1_7.dll怎么解决？x3daudio1_7.dll的5个修复方法
    牛客SQL实战
    map函数传入parseInt函数处理数字输出有误
    金融时间序列预测方法合集：CNN、LSTM、随机森林、ARMA预测股票价格（适用于时序问题）、相似度计算、各类评判指标绘图（数学建模科研适用）
    用HTML、CSS技术设计的个人网页与实现制作（web前端期末大作业）
    腾讯mini项目-【指标监控服务重构】2023-08-29
    做品牌定位，品牌三问是什么？
    算法提升：图的最小生成树算法-克鲁斯卡尔（Kruskal）
  • 原文地址：https://blog.csdn.net/m0_72618437/article/details/128028892