1028. 从先序遍历还原二叉树（三种方法：栈+递归+集合）

文章目录

• 1028. 从先序遍历还原二叉树（三种方法：栈+递归+集合）
• • 一、栈+ while迭代
  • • 1.思路
    • 2.代码
    • 二、递归法
    • • 1.思路
      • 2.代码
      • 三、集合存储
      • • 1.思路
        • 2.代���

          ---

          1028. 从先序遍历还原二叉树（三种方法：栈+递归+集合）

          ---

          一、栈+ while迭代

          1.思路

          1.遍历整个字符串，从0开始，根节点在第0层

          2.用level记录层数，每遇到一个-字符，当前层数+1

          3.用val记录要插入的结点的值，遍历取到的数字，通过字符运算得到值。

          4.找到当前要插入结点的父结点，栈的大小要小于当前层数

          5.如果节点只有一个子节点，那么保证该子节点为左子节点。

          6.将创建的新结点入栈

          7.除了根节点，其他子节点全部出栈，返回根节点

          2.代码

              public TreeNode recoverFromPreorder(String traversal) {        Stack stack = new Stack();        //用栈来存储结点        for (int i = 0; i  level) {                stack.pop();                //找到当前要插入结点的父结点            }            TreeNode node = new TreeNode(val);//创建新结点            if (!stack.isEmpty()) {                //如果节点只有一个子节点，那么保证该子节点为左子节点。                if (stack.peek().left == null) {                    stack.peek().left = node;                } else {                    stack.peek().right = node;                }            }            stack.add(node);//入栈        }        while (stack.size() > 1) {            stack.pop();            //要返回根节点，出到栈只有一个结点        }        return stack.pop();    }

          二、递归法

          1.思路

          1.利用helper函数，根据字符和对应深度创建结点，还原二叉树

          2.每遇到-字符，层数加一

          3.如果遍历的深度和获取到的深度不一致，返回空

          4.当深度等于层数时，下一个结点的位置从index + level开始

          5.通过字符运算获取数字，同时创建结点

          6.根节点的左树调用helper函数递归，如果左子节点是空，那么右子节点肯定也是空的

          7.如果根节点的左树不为空，要想添加结点，递归右树。

          8.最终返回根节点

          2.代码

              //102. 二叉树的层序遍历---递归写法    int index = 0;    //index记录遍历到字符串的哪个位置    public TreeNode recoverFromPreorder3(String traversal) {        return helper(traversal,0);    }    public TreeNode helper(String s, int depth) {        //helper函数用来创建二叉树        int level = 0;        //记录层数        while (index + level  
          三、集合存储
           
          1.思路
           
          1.使用正则匹配把字符串S拆成不同的数字存进数组中，用集合list来存储结点
          2.将根节点添加到list中，层数从1开始，不包括根节点
          3.数组存储的位置不为空时，根据转换的值创建结点
          4.将结点加入到集合中
          5.获取父结点，插入结点，并从新设置层数，果满了，层数加一
          6.最终返回根节点
           
          2.代码
           
              //102. 二叉树的层序遍历--正则匹配    public TreeNode recoverFromPreorder2(String traversal) {        String[] valus = traversal.split("-");        //使用正则匹配把字符串S拆成不同的数字，用集合list来存储结点        List list = new ArrayList();        list.add(new TreeNode(Integer.valueOf(valus[0])));//根节点        //根节点添加到list中        int level = 1;//层数层1开始，不包括根节点        for (int i = 1; i  
          点击移步博客主页，欢迎光临~