leetcode日记— 105. Construct Binary Tree from Preorder and Inorder Traversal

发布于 2020-10-06  118 次阅读


碎碎念:现在好像有点饿了,要不要买一包锅巴晚上吃呢 ?饿了就吃怎么减肥啊。难受。。都怪疫情在家吃太肥了。

题目如下:

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

总之就是数据结构非常经典的考题,当给出了前序遍历和中序遍历后,如何得到正确的树。

思路:

方法一:递归

先序遍历遍历到的节点确定了根节点(或者是当前子树的根节点),再使用中序遍历找到当前子树的根节点,就可以知道在什么区间内的节点是当前节点左子树节点的集合,什么区间内的节点是当前节点右子树节点的集合。递归函数返回当前节点,这样就完成了树的构建。

示意图如下(来自官方题解的解说视频):

先序遍历和中序遍历都设立左右指针,用指针表示在两数组中左右子树节点集合的边界

代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private Map<Integer,Integer> indexMap ;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<Integer,Integer>();
        int n = preorder.length;
        for(int i=0;i<n;i++){
            indexMap.put(inorder[i],i);
        }
        return buildTreeHelper(preorder,inorder,0,n-1,0,n-1);
    }
    public TreeNode buildTreeHelper(int[] preorder, int[] inorder, int pLeft, int pRight, int iLeft, int iRight){
        if(pLeft>pRight)
            return null;
        int pRoot = pLeft;
        int iRoot = indexMap.get(preorder[pLeft]);
        TreeNode root = new TreeNode(inorder[iRoot]);
        int sizeOfLeftSubTree = iRoot - iLeft;
        root.left = buildTreeHelper(preorder,inorder,pLeft+1,pLeft+sizeOfLeftSubTree,iLeft,iRoot-1);
        root.right = buildTreeHelper(preorder,inorder,pLeft+sizeOfLeftSubTree+1,pRight,iRoot+1,iRight);
        return root;
    }
}

方法二:迭代

以下思路借鉴的是leetcode题解区的大佬思路。

假设我们要还原的树是下图

    3
   / \
  9  20
    /  \
   15   7


首先假设我们只有先序遍历的数组,如果还原一颗树,会遇到什么问题。

preorder = [3, 9, 20, 15, 7 ]
首先我们把 3 作为根节点,然后到了 9 ,就出现一个问题,9 是左子树还是右子树呢?

所以需要再加上中序遍历的数组来确定。

inorder = [ 20, 9, 15, 3, 7 ]
我们知道中序遍历,首先遍历左子树,然后是根节点,最后是右子树。这里第一个遍历的是 20 ,说明先序遍历的 9 一定是左子树,利用反证法证明。

假如 9 是右子树,根据先序遍历 preorder = [ 3, 9, 20, 15, 7 ],说明根节点 3 的左子树是空的,

左子树为空,那么中序遍历就会先遍历根节点 3,而此时是 20,假设不成立,说明 9 是左子树。

接下来的 20 同理,所以可以目前构建出来的树如下。

      3
    /   
   9    
  / 
 20

或者换句话来说,一直遍历先序遍历数组,在出现与当前遍历到的中序遍历的值相同之前,所有先序遍历到的节点都是上一个节点的左孩子。而碰到了相同的之后,下一个节点则应该是右孩子。

但是问题来了,下一个节点15是谁的右孩子呢?

我们来假设几种情况,来想一下。

如果是 3 的右子树, 20 和 9 的右子树为空,那么中序遍历就是20 9 3 15。

如果是 9 的右子树,20 的右子树为空,那么中序遍历就是20 9 15。

如果是 20 的右子树,那么中序遍历就是20 15。

之前已经遍历的根节点是 3 9 20,把它倒过来,即20 9 3,然后和上边的三种中序遍历比较,会发现 15 就是最后一次相等的节点的右子树。

第 1 种情况,中序遍历是20 9 3 15,和20 9 3 都相等,所以 15 是3 的右子树。

第 2 种情况,中序遍历是20 9 15,只有20 9 相等,所以 15 是 9 的右子树。

第 3 种情况,中序遍历就是20 15,只有20 相等,所以 20 是 15 的右子树。

而此时我们的中序遍历数组是inorder = [ 20, 9 ,15, 3, 7 ],20 匹配,9匹配,最后一次匹配是 9,所以 15 是 9的右子树。

(对于上面的规律,我的理解是倒过来的先序遍历可以看作是从靠左边的节点一层一层往上找的过程,网上找的时候正好与中序遍历结果一样。最后一个相等的节点,根据中序遍历的定义,就是变为要得到右孩子的节点,因此最后一个相等的节点就是右孩子的父节点)

   3
  /
 9
/ \
2015   


综上所述,我们用一个栈保存已经遍历过的节点,遍历前序遍历的数组,一直作为当前根节点的左子树,直到当前节点和中序遍历的数组的节点相等了,那么我们正序遍历中序遍历的数组,倒着遍历已经遍历过的根节点(用栈的 pop 实现),找到最后一次相等的位置,把它作为该节点的右子树。

上边的分析就是迭代总体的思想,代码的话还有一些细节注意一下。用一个栈保存已经遍历的节点,用 curRoot 保存当前正在遍历的节点。

代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0)
            return null;
        // 栈用来装前序遍历的节点,当倒着遍历(也就是pop出栈时,可以找到前序遍历的下一个节点是谁的右子树--是与中序遍历相同的最后一个节点)
        Stack<TreeNode> preRoots = new Stack<TreeNode>();
        int preCount=0;
        int inCount=0;
        // cur类似于当前指针,用于遍历时建立树,root类似于头指针,用于返回值
        TreeNode curRoot = new TreeNode(preorder[preCount]);
        TreeNode root = curRoot;
        preCount++;
        preRoots.push(curRoot);
        while(preCount<preorder.length){
            if(curRoot.val==inorder[inCount]){
                //值相等则需要找是谁的右子树
                while(!preRoots.isEmpty()&&preRoots.peek().val==inorder[inCount]){
                    curRoot = preRoots.pop();
                    inCount++;
                }
                TreeNode node = new TreeNode(preorder[preCount]);
                curRoot.right = node;
                curRoot = curRoot.right;
                preRoots.push(curRoot);
                preCount++;
            }
            else{
// 若不一样的时候则为左子树
                TreeNode node = new TreeNode(preorder[preCount]);
                curRoot.left = node;
                curRoot = curRoot.left;
                preRoots.push(curRoot);
                preCount++;
            }
        }
        return root;
    }
}

我一开始忘记把新得到的curRoot push到栈里了,整了好久。。。


你好哇!欢迎来到雷公马碎碎念的地方:)