二叉樹的遍歷方式一般包括前序遍歷、中序遍歷以及后序遍歷：
-
前序遍歷：根結點 | 左子樹 | 右子樹
-
中序遍歷：左子樹 | 根結點 | 右子樹
-
后序遍歷：左子樹 | 右子樹 | 根結點
二叉樹遍歷的性質：
-
已知二叉樹的前序遍歷和中序遍歷可以唯一重建二叉樹；
-
已知二叉樹的中序遍歷和后序遍歷可以唯一重建二叉樹；
-
已知二叉樹的前序遍歷和后續遍歷不能唯一重構二叉樹，
采用遞回方式來實作二叉樹的重建：
- 遞回停止條件：遍歷結果的陣列長度為0；
- 遞回流程：通過找到根結點，從而將原始遍歷結果陣列切分為左子樹和右子樹的遍歷結果陣列，進行遞回，
- 前序遍歷結果陣列的第一個元素為根結點；
- 后續遍歷結果陣列的最后一個元素為根結點；
二叉樹的結點類：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
1. 已知前序遍歷和中序遍歷重建二叉樹——LeetCode105
class Solution {
public TreeNode buildTree(int[] pre, int[] in) {
// 遞回停止條件
if (pre.length == 0 && in.length == 0) return null;
// 首先構建根節點
TreeNode root = new TreeNode(pre[0]);
for (int i = 0; i < in.length; i++) {
// 找到中序遍歷中的根節點位置
if (in[i] == pre[0]) {
// 根據根節點的位置找到左子樹的前序遍歷和中序遍歷
// 遞回構建根節點的左子節點
root.left = buildTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
// 根據根節點的位置找到右子樹的前序遍歷和中序遍歷
// 遞回構建根節點的右子節點
root.right = buildTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
break;
}
}
return root;
}
}
Arrays.copyOfRange(int[] arr, int start, int end)用于復制陣列，其中arr為原始陣列，start是復制起始位置，end是復制結束位置，注意區間是左開右閉，即[start,end)，
2. 已知中序遍歷和后序遍歷重建二叉樹——LeetCode106
class Solution {
public TreeNode buildTree(int[] in, int[] post) {
if (in.length == 0 && post.length == 0) return null;
TreeNode root = new TreeNode(post[post.length - 1]);
for (int i = 0; i < in.length; i++) {
if (in[i] == post[post.length - 1]) {
root.left = buildTree(Arrays.copyOfRange(in, 0, i), Arrays.copyOfRange(post, 0, i));
root.right = buildTree(Arrays.copyOfRange(in, i + 1, in.length), Arrays.copyOfRange(post, i, post.length - 1));
break;
}
}
return root;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/56930.html
標籤：Java
上一篇：搭建輕量級的本地git