我们从二叉树的根节点root开始进行深度优先搜索。 在遍历中的每个节点处,我们输出D条短划线(其中D是该节点的深度),然后输出该节点的值。(如果节点的深度为D,则其直接子节点的深度为D+1。根节点的深度为0)。如果节点只有一个子节点,那么保证该子节点为左子节点。 给出遍历输出S,还原树并返回其根节点root。 示例 1: 输入:"1-2--3--4-5--6--7" 输出:[1,2,5,3,4,6,7]
示例 2:
输入:"1-2--3---4-5--6---7" 输出:[1,2,5,3,null,6,null,4,null,7]
示例 3:
输入:"1-401--349---90--88" 输出:[1,401,null,349,88,90]
提示: 原始树中的节点数介于1和1000之间。 每个节点的值介于1和10^9之间。
这题输入的是二叉树前序遍历的结果,让我们还原这颗二叉树。如果只给出二叉树的前序遍历结果我们是没法还原的。但这题还给出了两个条件,一个是每个数字前面的“-”表示当前节点的深度,一个是如果一个只有一个子节点,要保证这个子节点是左子节点。那么有了这两个条件,这颗二叉树基本上就能确定了。 我们看一下这题的解题思路: 首先创建一个栈,把创建的节点一个个压入到栈中。你会发现从栈底到栈顶每两个元素之间的关系是父子关系。画个图来看一下 通过上图我们可以发现从栈底到栈顶,1是2的父节点,2是3的父节点。其实还有一个最重要的发现就是栈中元素的个数-1就是栈顶元素的深度。这一个特性非常重要。这里要减1是因为树中节点的深度是从0开始的,不是从1开始,根节点的深度是0。
我们创建每个节点的时候,需要找到他的父节点,然后才能把当前节点挂到他的父节点下面。怎么找呢,就是通过栈中元素的个数来确定。看到这里估计代码大家都已经能写出来了,这里我们先来分开写。
第一步,找出当前节点的深度 //找出当前数字的深度,从0开始的,根节点是第0层 int level = 0; while (S.charAt(i) == '-') { level++; i++; }
第二步,找出当前节点的值 //找出当前节点的值 int val = 0; while (i < S.length() && S.charAt(i) != '-') { val = val * 10 + (S.charAt(i) - '0'); i++; }
第三步,找出当前节点的父节点,我们上面分析过,栈中元素的个数-1就栈顶节点的深度。这里一直循环,当栈中元素个数等于level的时候,说明栈顶元素就是当前节点的父节点。 //找到当前节点的父节点,子节点的深度要比父节点大1 while (stack.size() > 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);
通过上面我们把代码一步步拆解完之后我们再来看下完整代码。
public TreeNode recoverFromPreorder(String S) { Stack<TreeNode> stack = new Stack<>(); for (int i = 0; i < S.length(); ) { //找出当前数字的深度,从0开始的,根节点是第0层 int level = 0; while (S.charAt(i) == '-') { level++; i++; }
//找出当前节点的值 int val = 0; while (i < S.length() && S.charAt(i) != '-') { val = val * 10 + (S.charAt(i) - '0'); i++; }
//找到当前节点的父节点,子节点的深度要比父节点大1 while (stack.size() > 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(); }
题中说了节点是通过分隔符"-"隔开的,所以我们可以按照"-"把字符串拆开 //通过"-"分隔符把字符串拆开 String[] nodeValues = S.split("-");
这里不需要使用栈,我们可以使用一个list集合存储每层的节点,注意,每层只存储一个节点。我们直接可以通过get方法获取当前节点的父节点,也就是 TreeNode parent = list.get(level - 1);
这里大家可能有点困惑,每层那么多节点我们只存储一个,会不会把之前的给覆盖掉啊,其实会覆盖掉的,但没关系,如果被覆盖掉了,说明覆盖掉的节点以及他的子节点和子子节点……都已经被访问完了。我们不需要再访问了。
比如下面图中红色的节点3在第二层,当遍历到他的时候,就会把第二层的节点2给覆盖掉,覆盖掉了也没关系,因为节点2及他下面的所有子节点都已经被访问完了。 搞懂了上面的分析过程我们再来看下代码
public TreeNode recoverFromPreorder(String S) { //通过"-"分隔符把字符串拆开 String[] nodeValues = S.split("-"); List<TreeNode> list = new ArrayList<>(); //数组中的第一个值肯定是根节点,创建根节点然后添加到list中 list.add(new TreeNode(Integer.valueOf(nodeValues[0]))); //上面根节点已经加入到list中了,下面都是非根节点 int level = 1; for (int i = 1; i < nodeValues.length; i++) { if (!nodeValues[i].isEmpty()) { TreeNode node = new TreeNode(Integer.valueOf(nodeValues[i])); //因为是前序遍历,每层我们只需要存储一个结点即可,这个节点值有可能 //会被覆盖,如果被覆盖了说明这个节点以及他的子节点都以及遍历过了, //所以我们不用考虑被覆盖问题 list.add(level, node); //获取父节点 TreeNode parent = list.get(level - 1); //左子节点为空,优先添加到左子节点中 if (parent.left == null) { parent.left = node; } else { parent.right = node; } //深度要重新赋值 level = 1; } else { //统计节点的深度 level++; } } //返回树的根节点 return list.get(0); }
|