剑指 Offer 07. 重建二叉树

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   /   9  20
    /     15   7

思路

golang

对于任意一颗树而言，前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点preoder[0]。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

时间复杂度：O(n)，其中 n 是树中的节点个数。

空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间， 还有O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h < n，所以总空间复杂度为 O(n)。

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*先要搞清楚先序遍历和中序遍历的遍历顺序，
只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。
由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，
对上述形式中的所有左右括号进行定位。这样以来，我们就知道了左子树的前序遍历和中序遍历结果，
以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，
再将这两颗子树接到根节点的左右位置*/
func buildTree(preorder []int, inorder []int) *TreeNode {
	//遍历inorder中对应索引下标是否是preorder中的root节点
	for k := range inorder {
		if inorder[k] == preorder[0] {
			return &TreeNode{
				Val: preorder[0],
				//以root节点位置分割左右子树位置
				Left:  buildTree(preorder[1:k+1], inorder[:k]),
				Right: buildTree(preorder[k+1:], inorder[k+1:]),
			}
		}
	}
	return nil
}

js

//Definition for a binary tree node.
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (!preorder.length || !inorder.length) {
        return null;
    }

    const node = new TreeNode(preorder[0]);

    let i = 0; // i有两个含义，一个是根节点在中序遍历结果中的下标，另一个是当前左子树的节点个数
    for (; i < inorder.length;i++) {
        if (inorder[i] === preorder[0]) {
            break;
        }
    }

    node.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i));
    node.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1));
    return node;
};

剑指 Offer 07. 重建二叉树

原文：https://www.cnblogs.com/zmk-c/p/14608391.html