我們從二叉樹的根節點 root 開始進行深度優先搜索。

在遍歷中的每個節點處，我們輸出 D 條短劃線（其中 D 是該節點的深度），然后輸出該節點的值。（如果節點的深度為 D，則其直接子節點的深度為 D + 1。根節點的深度為 0）。

如果節點只有一個子節點，那么保證該子節點為左子節點。

給出遍歷輸出 S，還原樹并返回其根節點 root。

輸入：“1-2–3--4-5–6--7”
輸出：[1,2,5,3,4,6,7]

代碼

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode recoverFromPreorder(String S) {LinkedList<TreeNode> stack=new LinkedList<>();int pos=0;while (pos<S.length())//逐個遍歷{int level=0;while (S.charAt(pos)=='-')//獲取當前數字所在層數{pos++;level++;}int val=0;while (pos<S.length()&&Character.isDigit(S.charAt(pos)))//提取字符串的數字{val=val*10+(S.charAt(pos)-'0');pos++;}TreeNode temp=new TreeNode(val);if(stack.size()==level)//棧中元素等于層數，根據先序遍歷的特點說明當前是在左子樹{if(!stack.isEmpty())stack.getLast().left=temp;}else {//棧中元素不等于層數，根據先序遍歷的特點說明當前是在又子樹，需要先將左子樹出棧，才能獲得父節點while (stack.size()>level)stack.removeLast();stack.getLast().right=temp;}stack.add(temp);}while (stack.size()>1)stack.removeLast();return stack.getLast();}
}