106.md

✏️Leetcode基础刷题之(106. Construct Binary Tree from Inorder and ...)

2020-1-3 吴亲库里 库里的深夜食堂

---

✏️描述

这道题和上一题是一样的目的，构建二叉树。只是这道题给定二叉树的中序遍历和后序遍历，构建二叉树。(我们都知道要么给定先序遍历和中序遍历，要么给定中序遍历和后序遍历构建二叉树，如果是先序遍历和后序遍历是无法重现二叉树的，原因很简单，两种遍历都只能确定根节点的位置，不能确定左右子树)。

---

✏️题目实例

​

✏️题目分析

思路和上一题很像，还是需要先确定根节点。我们可以从后续遍历中得出根节点。肯定是最后一个元素。继而可以根据根节点到中序遍历中确定左右子树。反过来，根据中序遍历的分割我们也可以知道后续遍历的分割点。然后不断递归，构建左右子树。下面这张图有助于你理解下边的代码。其实代码也就是把昨天的递归稍微调整了一下。我觉得这两道题很有助于理解二叉树的遍历，印象会深一点。

​

---

 

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {

    /**
     * @param Integer[] $inorder 中序遍历
     * @param Integer[] $postorder  后序遍历
     * @return TreeNode
     */
    function buildTree($inorder, $postorder) {
        return $this->helper($inorder,0,count($inorder)-1,
                             $postorder,0,count($postorder)-1);
    }
    
    function helper(&$inorder,$ileft,$iright,&$postorder,$pleft,$pright)
{
        if($ileft>$iright || $pleft>$pright){
            return null;
        }
        $node=new TreeNode($postorder[$pright]);
        $i=0;
        for($i=$ileft;$i<=$iright;$i++){
        //每次先通过后序遍历中根节点的值(根节点就是数组最后一位)
        // 找到中序遍历的根节点位置
        // 就可以切分左右子树
            if($inorder[$i]==$node->val){
                break;
            }
        }
        //确认根节点的左子树
        $node->left=$this->helper($inorder,$ileft,$i-1,$postorder,
                                  $pleft,$pleft+$i-$ileft-1);
        //确认根节点的右子树                          
        $node->right=$this->helper($inorder,$i+1,$iright,$postorder,
                                   $pleft+$i-$ileft,$pright-1);
        return $node;
    }
}

---

如果觉得难理解，可以看看下面举的例子的过程。

​

联系

​