Leecode剑指 Offer 07. 重建二叉树

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

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

3
/ \
9 20
/ \
15 7

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析：

二叉树遍历规律：

前序遍历：【根节点，递归前序遍历左子树，递归前序遍历右子树】

中序遍历：【递归中序遍历左子树，根节点，递归中序遍历右子树】

发现前序遍历数组的第一个元素是根节点，中序遍历数组中以根节点作为枢轴（pivot)把左右子树分隔开来，这样可以在中序遍历的数组中获取左子树和右子树的长度，再在前序遍历数组根据左右子树各自的长度

切割出前序遍历数组中的对应的左子树和右子树数组，然后递归的寻找每个子树的根节点返回并作为左/右子节点赋给上一个节点，如下图所示：

递归执行第一遍：前序[3,9,20,15,7]，中序[9,3,15,20,7]，根节点为3，切分得到新的左子树前序[9]、中序[9]，右子树前序[20,15,7]、中序[15,20,7]

树：3
/ \
... ...

递归执行第二遍：前序[9]，中序[9]，长度只有1，故根节点是9，返回根节点

树：3
/ \
9 ...

递归执行第三遍：前序[20,15,7]，中序[15,20,7]，根节点是20，切分得到新的左子树前序[15]、中序[15]，右子树前序[7]、中序[7]，返回根节点

树：3
/ \
9 20

递归执行第四遍：前序[15]，中序[15]，长度只有1，故根节点是15，返回根节点

树：3
/ \
9 20
/
15

递归执行第五遍：前序[7]，中序[7]，长度只有1，故根节点是7，返回根节点，结束

树：3
/ \
9 20
/ \
15 7

递归解法：

 1 /**

 2  * Definition for a binary tree node.

 3  * function TreeNode(val) {

 4  *     this.val = val;

 5  *     this.left = this.right = null;

 6  * }

 7  */

 8 /**

 9  * @param {number[]} preorder

10  * @param {number[]} inorder

11  * @return {TreeNode}

12  */

13 var buildTree = function(preorder, inorder) {

14     if(preorder.length===0||inorder.length===0) return null;

15     let root = new TreeNode(preorder[0]);

16     if(preorder.length===1) return root;

17     let index =inorder.findIndex(e => e === root.val);

18     root.left = buildTree(preorder.slice(1,index+1), inorder.slice(0,index));

19     root.right = buildTree(preorder.slice(index+1), inorder.slice(index+1));

20

21     return root;

22 };

迭代解法：

分析：

//TODO

实现：

var buildTree = function(preorder, inorder) {

     if(preorder.length===0||inorder.length===0) return null;

    let root = new TreeNode(preorder[0]);

    let stack = [root];

    let inorderIndex = 0;

    let node;

    for(let i=1, len = preorder.length; i<len; i++) {

        let preorderVal = preorder[i];

        node = stack[stack.length-1];

        if(node.val !== inorder[inorderIndex]) {

            node.left = new TreeNode(preorderVal);

            stack.push(node.left);

        }else{

            while(stack.length!==0 && stack[stack.length-1].val===inorder[inorderIndex]){

                node = stack.pop();

                inorderIndex++;

            }

            node.right = new TreeNode(preorderVal);

            stack.push(node.right);

        }

    }

    return root;

};

巴特西

Leecode剑指 Offer 07. 重建二叉树

最新文章

热门文章