二叉树遍历:
先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树。
中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树。
后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。
二叉树遍历序列特点:
前序遍历序列:[根节点,[左子树],[右子树]]
中序遍历序列:[[左子树],根节点,[右子树]]
后序遍历序列:[[左子树],[右子树],根节点]
若要构造二叉树,只要能分别构建出根节点,根节点的左子树,根节点的右子树,那么就能完整地构造出二叉树
递归算法框架:
public TreeNode buildTree() {
// 找到根节点的值
int rootValue = ?;
// 构建根节点
TreeNode root = new TreeNode(rootValue);
// 构建根节点的左子树
root.left = buildTree();
// 构建根节点的右子树
root.right = buildTree();
return root;
}
1
/ \
2 3
/ \ / \
4 5 6 7
前序遍历序列:[1, 2, 4, 5, 3, 6, 7]
后序遍历序列:[4, 5, 2, 6, 7, 3, 1]
public TreeNode buildTree(int[] preorder, int[] postorder,
int preStart, int leftPreEnd,
int postStart, int postEnd) {
// 找到根节点的值
int rootValue = ?;
// 构建根节点
TreeNode root = new TreeNode(rootValue);
// 构建左子树
root.left = buildTree(preorder, postorder, ?, ?, ?, ?);
// 构建右子树
root.right = buildTree(preorder, postorder, ?, ?, ?, ?);
return root;
}
public TreeNode constructFromPrePost(
int[] preorder, int[] postorder,
int preStart, int preEnd,
int postStart, int postEnd) {
// 根节点值
int rootValue = preorder[preStart];
// 根节点索引
int rootIndex = preStart;
// 计算左子树 leftSize
// 前序序列第二个元素是左子树根节点
// 后序序列中和左子树根节点值相同的元素索引即左子树后序遍历序列右侧值
int leftSize = 0;
for (int i = postStart; i < postEnd; i++) {
if (postorder[i] == preorder[rootIndex + 1]) {
leftSize = i - postStart + 1;
}
}
// 构建根节点
TreeNode root = new TreeNode(rootValue);
// 左子树 preStart
int leftPreStart = rootIndex + 1;
// 左子树 preEnd
int leftPreEnd = leftPreStart + leftSize - 1;
// 左子树 postStart
int leftPostStart = postStart;
// 左子树 postEnd
int leftPostEnd = leftPostStart + leftSize - 1;
// 构建左子树
root.left = constructFromPrePost(preorder, postorder, leftPreStart, leftPreEnd, leftPostStart, leftPostEnd);
// 右子树 preStart
int rightPreStart = preStart + leftSize + 1;
// 右子树 preEnd
int rightPreEnd = preEnd;
// 右子树 postStart
int rightPostStart = postStart + leftSize;
// 右子树 postEnd
int rightPostEnd = postEnd - 1;
// 构建右子树
root.right = constructFromPrePost(preorder, postorder, rightPreStart, rightPreEnd, rightPostStart, rightPostEnd);
return root;
}
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
return constructFromPrePost(preorder, postorder, 0, preorder.length - 1, 0, postorder.length - 1);
}