1028. 从先序遍历还原二叉树

迈不过友情╰ 2023-02-19 14:26 1阅读 0赞

# 题目： #

https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/

> 我们从二叉树的根节点 root 开始进行深度优先搜索。
> 
> 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为  
> D + 1。根节点的深度为 0）。
> 
> 如果节点只有一个子节点，那么保证该子节点为左子节点。
> 
> 给出遍历输出 S，还原树并返回其根节点 root。  
> case1：  
> 输入：“1-2–3--4-5–6--7”  
> 输出：\[1,2,5,3,4,6,7\]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDkwMTMyOQ_size_16_color_FFFFFF_t_70]

# 思路 #

1.  本题给出一个二叉树先序遍历的结果，然后让根据先序遍历的结果还原二叉树
2.  采用递归的思想，S是先续遍历的结果，所以S中字符的顺序肯定是**当前节点 + 左子树的遍历结果 + 右子树的遍历结果** ，首先根据S得到当前节点，然后递归调用函数，通过S构建左子树，然后再通过S构建右子树。
3.  类似于通过先续遍历结果构建二叉树的思想，核心思想是通过一个index下标进行S遍历位置的标记， 然后通过**构建当前节点+ 递归调用**的思想进行code。
4.  本题的变式在于对 **在只有一个节点时一定是左节点的前提下，当前节点所处层级和 期望的层级进行比较， 只有当相同时才可以进行节点的构建，其他情况表示当前节点和当前位置不匹配，**

# code #

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    
     /* 根据先序遍历构造一个二叉树， 可以采用递归的思想，先根据S构造 不对输入的特殊情况进行检查 */
    class Solution { 
        private int index = 0;
    
        public TreeNode recoverFromPreorder(String S) { 
            if (S == null || S.length() == 0) { 
                return null;
            }
            return buildTree(S, 0);
        }
    
        private TreeNode buildTree(String s, int expectLevel) { 
            if (s == null || s.length() == index) { 
                return null;
            }
            int i = index;
            while (i < s.length() && s.charAt(i) == '-') { 
                i++;
            }
            int level = i - index;
    
            if (level != expectLevel) { 
                return null;
            }
    
            int num = 0;
            while (i < s.length() && s.charAt(i) != '-' ) { 
                num = num * 10 + (s.charAt(i) - '0');
                i++;
            }
            TreeNode node = new TreeNode(num);
            index = i;
            node.left = buildTree(s, level + 1);
            node. right = buildTree(s, level + 1);
            return node;
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDkwMTMyOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200621083528817.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDkwMTMyOQ==,size_16,color_FFFFFF,t_70