public TreeNode recoverFromPreorder(String S) { Stack<TreeNode> path = new Stack<>(); //构建好栈 //定义一个变量来遍历S int i = 0; //定义一个int变量来确定节点的层数 //先将S转换成char[] char[] s = S.toCharArray(); //开始遍历S while(i<s.length){ int level = 0; //先确定层数 while(s[i] == '-'){ ++i; ++level; } //再确定结点的值 //先将值初始化为0 int value = 0; while(i<s.length && Character.isDigit(s[i])){ value = value * 10 + s[i] - '0'; ++i; } //构造树的结点 TreeNode node = new TreeNode(value); //插入到正确位置 if(level == path.size()){ if(!path.isEmpty()) { path.peek().left = node; } }else{ while (level < path.size()){ path.pop(); } path.peek().right = node; } path.push(node); } while (path.size() > 1){ path.pop(); } return path.peek(); }
只是看懂了官方题解又默写了一遍而已……太难了,我脑子跟不上……想哭………………
——2020.6.20