逆推二叉树
根据中序、后序得到二叉树。根据中序、前序得到二叉树。
二叉树的层序遍历
假设现在有一颗二叉树如下
其中序遍历为： CBAEDF （左 - 根- 右）
其后序遍历为：CBEFDA （左 - 右 - 根）
其前序遍历为：ABCDEF （根 - 左 - 右）
如果我们现在只知道中序和后序，或者中序和前序。如何构建出二叉树。
假设已知中序和后序，构建过程如下。
1
2
3
4
5
| 1. 根据后序（CBEFDA）， 可以知道根节点为最后一个节点。即节点A。
2. 拿到根节点A以后，根据中序（CBAEDF）， A左边的是A的左子树，A右边的是A的右子树。
3. 根据根节点的位置来判断左子树和右子树的左右边界条件，以便于后续二叉树构建。
4. 分别递归构建左子树和右子树。
5. 返回根节点。
|
参数定义：
inorderStartIndex: 构建子树时，中序遍历数组中的起始位置；
inorderEndIndex： 构建子树时，中序遍历数组中的结束位置；
postorderStartIndex: 后序遍历数组中的起始位置；
postorderEndIndex： 后序遍历数组中的结束位置。
rootIndex： 当前构建树的根节点在中序数组中的index
每次递归构建子树时的起始下标和结束下标的计算：
根据中序遍历，根节点位置确定以后，根节点左边为左子树，右边为右子树。那么就需要确定左子树的起始边界和右子树的起始边界。
已知A左边的就是左子树，所以对应的后序遍历数组中，下一次遍历左右起始位置如下
1
2
3
4
5
6
| 1. 左子树：
中序数组： 起始位置： inorderStartIndex 结束位置： rootIndex-1
后序数组： 起始位置： postorderStartIndex 结束位置： postorderStartIndex + (rootIndex - inorderStartIndex) - 1
2. 右子树：
中序数组： 起始位置： rootIndex+1 结束位置： inorderEndIndex
后序数组： 起始位置： postorderStartIndex + (rootIndex - inorderStartIndex) 结束位置： postorderEndIndex
|
假设已知中序和前序
与上述一样，只是在确定起始位置的时候有所不同。
根据前序可以知道根节点。即为前序数组的第一个元素。则计算的起始位置为：
1
2
3
4
5
6
| 1. 左子树：
中序数组： 起始位置： inorderStartIndex 结束位置： rootIndex-1
后序数组： 起始位置： postorderStartIndex 结束位置： postorderStartIndex + (rootIndex - inorderStartIndex) - 1
2. 右子树：
中序数组： 起始位置： rootIndex+1 结束位置： inorderEndIndex
后序数组： 起始位置： postorderStartIndex + (rootIndex - inorderStartIndex) 结束位置： postorderEndIndex
|
代码
定义树节点
1
2
3
4
5
6
7
8
9
| class TreeNode<T> {
T val;
TreeNode left;
TreeNode right;
public TreeNode(T val) {
this.val = val;
}
}
|
中序+后序
为了方便在中序数组中获取到根节点的索引，可以把中序遍历的所有数据放在一个map里面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
private Map<Character, Integer> indexMap = new HashMap<>();
private TreeNode<Character> getTreeByInorderAndPostorder(String postorder, String inorder) {
for (int i = 0; i < inorder.length(); i++) {
indexMap.put(inorder.charAt(i), i);
}
return buildTreeByInorderAndPostorder(0, inorder.length() - 1, 0, posts.length - 1, postorder.toCharArray());
}
private TreeNode<Character> buildTreeByInorderAndPostorder(int inorderStartIndex, int inorderEndIndex, int postorderStartIndex, int postorderEndIndex, char[] posts) {
if (inorderStartIndex > inorderEndIndex || postorderStartIndex > postorderEndIndex) {
return null;
}
char rootVal = posts[postorderEndIndex];
int rootIndex = indexMap.get(rootVal);
TreeNode<Character> root = new TreeNode<>(rootVal);
root.left = buildTreeByInorderAndPostorder(inorderStartIndex, rootIndex - 1, postorderStartIndex, postorderStartIndex + rootIndex - inorderStartIndex - 1, posts);
root.right = buildTreeByInorderAndPostorder(rootIndex + 1, inorderEndIndex, postorderStartIndex + rootIndex - inorderStartIndex, postorderEndIndex - 1, posts);
return root;
}
}
|
中序+前序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| private TreeNode<Character> getTreeByInorderAndPreorder(String inorder, String preorder) {
for (int i = 0; i < inorder.length(); i++) {
indexMap.put(inorder.charAt(i), i);
}
return buildTreeByInorderAndPreorder(0, inorder.length() - 1, 0, preorder.length() - 1, preorder.toCharArray());
}
private TreeNode<Character> buildTreeByInorderAndPreorder(int inorderStartIndex, int inorderEndIndex,
int preorderStartIndex, int preorderEndIndex,
char[] preorder) {
if (inorderStartIndex > inorderEndIndex || preorderStartIndex > preorderEndIndex) return null;
char rootVal = preorder[preorderStartIndex];
int rootIndex = indexMap.get(rootVal);
TreeNode<Character> root = new TreeNode<>(rootVal);
root.left = buildTreeByInorderAndPreorder(inorderStartIndex, rootIndex - 1, preorderStartIndex + 1, preorderStartIndex + rootIndex - inorderStartIndex, preorder);
root.right = buildTreeByInorderAndPreorder(rootIndex + 1, inorderEndIndex, preorderStartIndex + rootIndex - inorderStartIndex + 1, preorderEndIndex, preorder);
return root;
}
|
二叉树的层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
private String levelTraverse(TreeNode<Character> root) {
StringBuilder sb = new StringBuilder();
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode<Character> node = queue.poll();
sb.append(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return new String(sb);
}
|