---

1028. 從先序遍歷還原二叉樹（三種方法：棧+遞歸+集合）

---

一、棧+ while迭代

1.思路

1.遍歷整個字符串，從0開始，根節點在第0層
2.用level記錄層數，每遇到一個-字符，當前層數+1
3.用val記錄要插入的結點的值，遍歷取到的數字，通過字符運算得到值。
4.找到當前要插入結點的父結點，棧的大小要小于當前層數
5.如果節點只有一個子節點，那么保證該子節點為左子節點。
6.將創建的新結點入棧
7.除了根節點，其他子節點全部出棧，返回根節點

2.代碼

    public TreeNode recoverFromPreorder(String traversal) {Stack<TreeNode> stack = new Stack<>();//用棧來存儲結點for (int i = 0; i < traversal.length(); ) {//遍歷整個字符串，從0開始，根節點在第0層int level = 0;//記錄當前層數while (traversal.charAt(i) == '-') {//每遍歷到一個-，層數累加level++;i++;}int val = 0;//查看當前要插入結點的數字while (i < traversal.length() && traversal.charAt(i) != '-') {//當前的字符是數字，并且未超過字符串val = val * 10 + (traversal.charAt(i) - '0');//根據字符的相加，遍歷字符串找數字時 只能一個數字一個數字的轉，// 但是字符串中連續的數字是一個多位數，需要前面的數字*10變高位，再加上后面的數，// 成為一個數，作為新結點的值i++;}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();}

二、遞歸法

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 < s.length() && s.charAt(index + level) == '-') {level++;}//如果遍歷的深度和獲取到的深度不一致，返回空if (level != depth){return null;}int next = index + level;//獲取數字while (next < s.length() && s.charAt(next) != '-')next++;int val = Integer.parseInt(s.substring(index + level, next));index = next;//創建結點TreeNode root = new TreeNode(val);root.left = helper(s, depth + 1);if (root.left == null) {//如果左子節點是空，那么右子節點肯定也是空的root.right = null;} else {root.right = helper(s, depth + 1);}return root;}

三、集合存儲

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<TreeNode> list = new ArrayList<>();list.add(new TreeNode(Integer.valueOf(valus[0])));//根節點//根節點添加到list中int level = 1;//層數層1開始，不包括根節點for (int i = 1; i < valus.length; i++) {if (!valus[i].isEmpty()) {//數組存儲的位置不為空TreeNode node = new TreeNode(Integer.valueOf(valus[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);}

點擊移步博客主頁，歡迎光臨~