PHPer面试必看：分门别类带你撸《剑指Offer》之二叉树

摘要：例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。操作给定的二叉树，将其变换为源二叉树的镜像。剑指中还有一道类似的变种题目，就是下面的这道，之字形遍历二叉树。最后下面的两道题目分别运用了二叉树先序中序遍历算法。

以下内容可能偏应试但很好理解，所以大家一定要坚持看下去，因为我们变强的过程注定孤独的，坚持下来就会看到明天的太阳。

我们接着说说你理解的二叉树吧这篇文章来的。下面我们来快速复习下二叉树相关的概念：

度：特定父节点的子节点的总数被称为它的度数。

路径：从源节点到目标节点的节点和边的序列称为两个节点之间的路径。

节点的高度：节点的高度由节点与最深节点之间的边数决定。

树的高度：树的高度是由它的根节点的高度定义的。

深度：节点的深度由节点和根节点之间的边数决定。

还有二叉树的分类相关的概念：

二叉搜索树：二叉搜索树（BST）是一种特殊类型的二叉树，其中节点以排序的方式存储，即在任何给定的点上，节点值必须大于或等于左子节点值，小于右子节点值。

自平衡二叉树：自平衡二叉搜索树或高度平衡二叉搜索树是一种特殊类型的二叉搜索树，它试图通过自动调整来尽量保持树的高度或层次尽可能小。

常见平衡二叉树的类型：

AA树

AVL树

红黑树

这些基础的内容，大家不明白的话可以前往开头提到的文章查看详细内容。

那我们废话不多说，来看《剑指Offer》中的第一个关于Tree的题目。

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路分析：根据二叉树前序遍历的特点（根-左-右），每次读取的第一个值一定是根节点，这样我们可以在中序遍历的序列中找到当前的根节点的位置。

根据中序遍历的特点（左-根-右），当确定了一个根节点后，其左边序列就是这个根节点的左子树，右边序列就是其右子树。

我们每次都需要在前序遍历中找根节点并创建一个根节点，然后在中序遍历中确定根节点位置，并确定当前根节点的左右子树，然后以同样的方法去构建左右子树。

这就是一个递归的过程。什么是递归？不慌，不清楚的同学可以看我之前写的什么是递归，一定要弄清楚递归，因为下面的题目中会大量运用到递归的思想。

来看下具体代码实现：

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/

function reConstructBinaryTree($pre, $vin)
{
    if (empty($pre) || empty($vin)) {
        return null;
    }
    //在前序中寻找根节点
    $root = new TreeNode($pre[0]);
    //确定根节点在中序遍历中的位置
    $indexInVin = array_search($pre[0], $vin, true);
    //左子树先序遍历结果
    $leftPrev = array_slice($pre, 1, $indexInVin); 
    //左子树中序遍历结果
    $leftVin = array_slice($vin, 0, $indexInVin); 
    //右子树先序遍历结果
    $rightPrev = array_slice($pre, $indexInVin + 1);
    //右子树中序遍历结果
    $rightVin = array_slice($vin, $indexInVin + 1);
    //递归构建树
    $root->left = reConstructBinaryTree($leftPrev, $leftVin);
    $root->right = reConstructBinaryTree($rightPrev, $rightVin);
    //返回根节点
    return $root;
}

完整的代码在这里，需要的同学可以点击查看。

好了，我们继续。来看第二道。

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路分析：第一种情况如果根节点相同，那么就分别去子节点里面匹配。不符合的话看
第二种情况，如果根节点不同，就去用pRoot1的左孩子和pRoot2去比较。还不符合的话就尝试用pRoot1的右孩子和pRoot2去比较。

还是递归的运用，看下面的解答。

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/
function HasSubtree($pRoot1, $pRoot2)
{
    if (empty($pRoot1) || empty($pRoot2)) {
        return false;
    }
    return isSubtree($pRoot1, $pRoot2) || HasSubtree($pRoot1->left, $pRoot2)
    || HasSubtree($pRoot1->right, $pRoot2);
}
function isSubtree($pRoot1, $pRoot2)
{
    if (empty($pRoot2)) {
        return true;
    }
    if (empty($pRoot1)) {
        return false;
    }
    return $pRoot1->val === $pRoot2->val && isSubtree($pRoot1->left, $pRoot2->left) && isSubtree($pRoot1->right, $pRoot2->right);
}

来看下一道。

操作给定的二叉树，将其变换为源二叉树的镜像。

这个题目很有名哈，可能你也经常看到。但是不难，10行代码就搞定了。依然要使用递归的思想，看代码的话秒懂哦。

val = $val;
    }
}*/
//https://www.zhihu.com/question/31202353?rf=31230953
//操作给定的二叉树，将其变换为源二叉树的镜像。
function Mirror(&$root)
{
    if (empty($root)) {
        return;
    }
    $left = $root->left;
    $right = $root->right;
    $root->right = $left;
    $root->left = $right;
    Mirror($root->left);
    Mirror($root->right);
}

接着来看一道关于层次遍历二叉树的题目，除了层次遍历之外，我们还应当掌握先序，中序，后续遍历二叉树的递归算法以及非递归算法，除此之外还有节点的搜索、新增以及删除等常用操作都在这里了。

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路分析:我们需要建立一个队列，先将根节点入队，然后将队首出队，然后判断它的左右子树是否为空，不为空，则先将左子树入队，然后右子树入队。

function PrintFromTopToBottom($root)
{
    $traverse = [];
    array_push($traverse, $root->val);
    inQueue($root, $traverse);
    return $traverse;
}
function inQueue($node, &$return)
{
    if (empty($node)) {
        return;
    }
    if ($left = $node->left) {
        array_push($return, $left->val);
    }
    if ($right = $node->right) {
        array_push($return, $right->val);
    }
    inQueue($left, $return);
    inQueue($right, $return);
}

此题还有非递归的解法，点击这里可以看到源代码。

恭喜，你坚持看到这里了，真棒！我们继续。

《剑指Offer》中还有一道类似的变种题目，就是下面的这道，之字形遍历二叉树。

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路分析：当我们在打印某一行的结点时，把下一层的结点保存到相应的栈中。如果当前打印的是奇数层，则先保存左子结点再保存右子结点到一个栈中；如果当前打印的是偶数层，则先保存右子结点再保存左子结点到另一个栈中。

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/

function MyPrint($pRoot)
{
    if (empty($pRoot)) return [];
    $cur = 0;
    $next = 1;
    $stack[0] = [];
    $stack[1] = [];
    array_push($stack[0], $pRoot);
    $i = 0;
    $return = [];
    $return[0] = [];
    while (!empty($stack[$cur]) || !empty($stack[$next])) {
        $top = array_pop($stack[$cur]);
        array_push($return[$i], $top->val);
        if ($cur == 0) {
            if ($left = $top->left) {
                array_push($stack[$next], $left);
            }
            if ($right = $top->right) {
                array_push($stack[$next], $right);
            }
        } else {
            if ($right = $top->right) {
                array_push($stack[$next], $right);
            }
            if ($left = $top->left) {
                array_push($stack[$next], $left);
            }
        }
        if (empty($stack[$cur])) {
            $cur = 1 - $cur;
            $next = 1 - $next;
            if (!empty($stack[0]) || !empty($stack[1])) {
                $i++;
                $return[$i] = [];
            }
        }
    }
    return $return;
}

好了，现在老铁你可以去喝个水休息一下，因为还有不少题目等待着我们，如果累了你可以先按个赞标记一下，明天接着看。另外源代码点击这里查看，老铁也可以先star一下，以后再看，您的star是我更新的动力。

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路分析：BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。完美的递归定义。

function VerifySquenceOfBST($sequence)
{
    if (count($sequence) == 0) return false;
    if (count($sequence) == 1) return true;
    
    if ($sequence) {
        $length = count($sequence);
        
         if ($length == 2) {
            if ($sequence[0] < $sequence[1]) return true;
        }
        
        $root = $sequence[$length - 1];
        $left = [];
        $right = [];
        $leftFlag = false;
        $rightFlag = false;
        $i = 0;
        while($sequence[$i] < $root) {
            array_push($left, $sequence[$i]);
            $i++;
        }
        $i === count($left) && $leftFlag = true;
        $j = $i;
        while($sequence[$j] > $root) {
             array_push($right, $sequence[$j]);
             $j++;
        }
        ($j === ($length - 1)) && $rightFlag = true;
        if ($leftFlag && $rightFlag) {
            if ($left && $right) {
                return VerifySquenceOfBST($left) && VerifySquenceOfBST($right);
            } elseif ($left) {
                return VerifySquenceOfBST($left);
            } else {
                return VerifySquenceOfBST($right);
            }
        } else {
            return false;
        }
    }
    return true;
}

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路分析：利用递归遍历所有路径。

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/
function FindPath($root, $expectNumber)
{
    if (empty($root)) return [];
    $a = $q = [];
    buildPath($root, $expectNumber, $q, $a);
    return $a;
}
function buildPath($node, $sum, $q, &$a)
{
    if ($node) {
        $q[] = $node->val;
        $sum -= $node->val;
        if ($sum > 0) {
            buildPath($node->left, $sum, $q, $a);
            buildPath($node->right, $sum, $q, $a);
        } elseif (empty($node->left) && empty($node->right) && $sum == 0) {
            $a[] = $q;
        }
    }
}

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路分析：方法一：递归版

1.将左子树构造成双链表，并返回链表头节点。

2.定位至左子树双链表最后一个节点。

3.如果左子树链表不为空的话，将当前root追加到左子树链表。

4.将右子树构造成双链表，并返回链表头节点。

5.如果右子树链表不为空的话，将该链表追加到root节点之后。

6.根据左子树链表是否为空确定返回的节点。

function Convert($pRootOfTree)
{
    // write code here
    if (empty($pRootOfTree)) {
        return null;
    }
    if (empty($pRootOfTree->left) && empty($pRootOfTree->right)) {
        return $pRootOfTree;
    }
    //将左子树构造成双链表，并返回链表头节点。
    $left = Convert($pRootOfTree->left);
    $temp = $left;
    // 2.定位至左子树双链表最后一个节点。
    while($temp !== null && $temp->right != null) {
        $temp = $temp->right;
    }
    // 3.如果左子树链表不为空的话，将当前root追加到左子树链表。
    if ($left != null) {
        $temp->right = $pRootOfTree;
        $pRootOfTree->left = $temp;
    }
    // 4.将右子树构造成双链表，并返回链表头节点。
    $right = Convert($pRootOfTree->right);
    // 5.如果右子树链表不为空的话，将该链表追加到root节点之后。
    if ($right != null) {
        $right->left = $pRootOfTree;
        $pRootOfTree->right = $right;
    }
    return $left != null ? $left : $pRootOfTree;
}

非递归算法
解题思路：

1.核心是中序遍历的非递归算法(对的，就是上文提到的那个中序遍历算法)。

2.修改当前遍历节点与前一遍历节点的指针指向。

function ConvertNotRecursive($pRootOfTree)
{
    if (empty($pRootOfTree)) {
        return null;
    }
    $stack = new SplStack();
    $p = $pRootOfTree;
    // 用于保存中序遍历序列的上一节点
    $pre = null;
    $isFirst = true;
    
    while ($p || !$stack->isEmpty()) {
        while($p) {
            $stack->push($p);
            $p = $p->left;
        }
        $p = $stack->pop();
        if ($isFirst) {
            // 将中序遍历序列中的第一个节点记为root
            $pRootOfTree = $p;
            $pre = $pRootOfTree;
            $isFirst = false;
        } else {
            $pre->right = $p;
            $p->left = $pre;
            $pre = $p;
        }
        $p = $p->right;
    }
    return $pRootOfTree;
}

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路分析：最直接的做法，遍历每个结点，借助一个获取树深度的递归函数，根据该结点的左右子树高度差判断是否平衡，然后递归地对左右子树进行判断。

function IsBalanced_Solution($pRoot)
{
    if (empty($pRoot)) return true;
    return abs(maxDepth($pRoot->left) - maxDepth($pRoot->right)) <= 1 &&
        IsBalanced_Solution($pRoot->left) && IsBalanced_Solution($pRoot->right);
}
function maxDepth($node)
{
    if (empty($node)) return 0;
    return 1 + max(maxDepth($node->left), maxDepth($node->right));
}

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路分析：二叉树的下一个节点，一共有以下情况：

1.二叉树为空，则返回空；

2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；

3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。

function GetNext($pNode)
{
    if (empty($pNode)) return null;
    if ($right = $pNode->right) {
        $currentNode = $right;
        while ($currentNode->left) {
            $currentNode = $currentNode->left;
        }
        return $currentNode;
    }
    
    while ($pNode->next) {
        $parent = $pNode->next;
        if ($parent->left === $pNode) {
            return $parent;
        }
        $pNode = $pNode->next;
    }
    return null;
}

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路分析：首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同，左子树的右子树和右子树的左子树相同即可，采用递归。非递归也可，采用栈或队列存取各级子树根节点。

function isSymmetrical($pRoot)
{
    // write code here
    if (empty($pRoot)) return true;
    
    return compare($pRoot->left, $pRoot->right);
}
function compare($left, $right)
{
    if ($left === null) return $right === null;
    if ($right === null) return false;
    if ($left->val != $right->val) return false;
    return compare($left->right, $right->left) && compare($left->left, $right->right);
}

可以看到递归的强大，合适运用的时候真的是事半功倍。最后下面的两道题目分别运用了二叉树先序、中序遍历算法。

请实现两个函数，分别用来序列化和反序列化二叉树

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/
function MySerialize($pRoot)
{
    $arr = [];
    doSerialize($pRoot, $arr);
    return implode(",", $arr);
}
function doSerialize($pRoot, &$arr)
{
    if (empty($pRoot)) {
        $arr[] = "#";
        return;
    }
    $arr[] = $pRoot->val;
    doSerialize($pRoot->left, $arr);
    doSerialize($pRoot->right, $arr);
}
function MyDeserialize($s)
{
    $arr = explode(",", $s);
    $i = -1;
    return doDeserialize($arr, $i); 
}
function doDeserialize($arr, &$i)
{
    $i++;
    if ($i >= count($arr)) {
        return null;
    }
    if ($arr[$i] == "#") return null;
    $node = new TreeNode($arr[$i]);
    $node->left = doDeserialize($arr, $i);
    $node->right = doDeserialize($arr, $i);
    return $node;
}

给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/
function KthNode($pRoot, $k)
{
    $traverse = inOrderTraverse($pRoot);
    if ($k <= count($traverse)) {
        return $traverse[$k - 1];
    }
    return null;
}
function inOrderTraverse($pRoot)
{
    $traverse = [];
    if ($left = $pRoot->left) {
        $traverse = array_merge($traverse, inOrderTraverse($left));
    }
    array_push($traverse, $pRoot);
    if ($right = $pRoot->right) {
        $traverse = array_merge($traverse, inOrderTraverse($right));
    }
    return $traverse;
}

PHP基础数据结构专题系列目录地址：地址 主要使用PHP语法总结基础的数据结构和算法。还有我们日常PHP开发中容易忽略的基础知识和现代PHP开发中关于规范、部署、优化的一些实战性建议，同时还有对Javascript语言特点的深入研究。