LeetCode–重建二叉樹
博客說明
文章所涉及的資料來自互聯網整理和個人總結，意在于個人學習和經驗匯總，如有什么地方侵權，請聯系本人洗掉，謝謝！
介紹
劍指 Offer 07. 重建二叉樹
主站 105 題
題目
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建該二叉樹，假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字，
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
回傳如下的二叉樹：
3
/ \
9 20
/ \
15 7
思路
- 使用前序遍歷的第一個元素創建根節點，
- 創建一個堆疊，將根節點壓入堆疊內，
- 初始化中序遍歷下標為 0，
- 遍歷前序遍歷的每個元素，判斷其上一個元素（即堆疊頂元素）是否等于中序遍歷下標指向的元素，
- 若上一個元素不等于中序遍歷下標指向的元素，則將當前元素作為其上一個元素的左子節點，并將當前元素壓入堆疊內，
- 若上一個元素等于中序遍歷下標指向的元素，則從堆疊內彈出一個元素，同時令中序遍歷下標指向下一個元素，之后繼續判斷堆疊頂元素是否等于中序遍歷下標指向的元素，若相等則重復該操作，直至堆疊為慷訓者元素不相等，然后令當前元素為最后一個想等元素的右節點，
- 遍歷結束，回傳根節點
代碼
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || preorder.length == 0){
return null;
}
//前序遍歷第一個為根節點
TreeNode root = new TreeNode(preorder[0]);
int length = preorder.length;
Stack<TreeNode> stack = new Stack<TreeNode>();
//將根節點壓入堆疊
stack.push(root);
int index = 0;
for(int i = 1;i<length;i++){
int preorderVal = preorder[i];
//查看堆疊頂的物件
TreeNode node = stack.peek();
if(node.val != inorder[index]){ //判斷中序遍歷的物件是否為當前堆疊頂元素
node.left = new TreeNode(preorderVal);
stack.push(node.left);
}else{
while(!stack.isEmpty() && stack.peek().val == inorder[index]){
node = stack.pop();
index++;
}
node.right = new TreeNode(preorderVal);
stack.push(node.right);
}
}
return root;
}
}
感謝
Leetcode
以及勤勞的自己
關注公眾號： 歸子莫，獲取更多的資料，還有更長的學習計劃
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/38601.html
標籤：Java