PHPer面試必看：分門別類帶你擼《劍指Offer》之二叉樹

li21 發(fā)布于2019-07-01 10:26 / 2603人閱讀

摘要：例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。操作給定的二叉樹，將其變換為源二叉樹的鏡像。劍指中還有一道類似的變種題目，就是下面的這道，之字形遍歷二叉樹。最后下面的兩道題目分別運用了二叉樹先序中序遍歷算法。

開篇

以下內(nèi)容可能偏應(yīng)試但很好理解，所以大家一定要堅持看下去，因為我們變強(qiáng)的過程注定孤獨的，堅持下來就會看到明天的太陽。

回顧

我們接著說說你理解的二叉樹吧這篇文章來的。下面我們來快速復(fù)習(xí)下二叉樹相關(guān)的概念：

度：特定父節(jié)點的子節(jié)點的總數(shù)被稱為它的度數(shù)。

路徑：從源節(jié)點到目標(biāo)節(jié)點的節(jié)點和邊的序列稱為兩個節(jié)點之間的路徑。

節(jié)點的高度：節(jié)點的高度由節(jié)點與最深節(jié)點之間的邊數(shù)決定。

樹的高度：樹的高度是由它的根節(jié)點的高度定義的。

深度：節(jié)點的深度由節(jié)點和根節(jié)點之間的邊數(shù)決定。

還有二叉樹的分類相關(guān)的概念：

二叉搜索樹：二叉搜索樹（BST）是一種特殊類型的二叉樹，其中節(jié)點以排序的方式存儲，即在任何給定的點上，節(jié)點值必須大于或等于左子節(jié)點值，小于右子節(jié)點值。

自平衡二叉樹：自平衡二叉搜索樹或高度平衡二叉搜索樹是一種特殊類型的二叉搜索樹，它試圖通過自動調(diào)整來盡量保持樹的高度或?qū)哟伪M可能小。

常見平衡二叉樹的類型：

AA樹

AVL樹

紅黑樹

這些基礎(chǔ)的內(nèi)容，大家不明白的話可以前往開頭提到的文章查看詳細(xì)內(nèi)容。

熱身

那我們廢話不多說，來看《劍指Offer》中的第一個關(guān)于Tree的題目。

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

思路分析：根據(jù)二叉樹前序遍歷的特點（根-左-右），每次讀取的第一個值一定是根節(jié)點，這樣我們可以在中序遍歷的序列中找到當(dāng)前的根節(jié)點的位置。

根據(jù)中序遍歷的特點（左-根-右），當(dāng)確定了一個根節(jié)點后，其左邊序列就是這個根節(jié)點的左子樹，右邊序列就是其右子樹。

我們每次都需要在前序遍歷中找根節(jié)點并創(chuàng)建一個根節(jié)點，然后在中序遍歷中確定根節(jié)點位置，并確定當(dāng)前根節(jié)點的左右子樹，然后以同樣的方法去構(gòu)建左右子樹。

這就是一個遞歸的過程。什么是遞歸？不慌，不清楚的同學(xué)可以看我之前寫的什么是遞歸，一定要弄清楚遞歸，因為下面的題目中會大量運用到遞歸的思想。

來看下具體代碼實現(xiàn)：

/*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;
    }
    //在前序中尋找根節(jié)點
    $root = new TreeNode($pre[0]);
    //確定根節(jié)點在中序遍歷中的位置
    $indexInVin = array_search($pre[0], $vin, true);
    //左子樹先序遍歷結(jié)果
    $leftPrev = array_slice($pre, 1, $indexInVin); 
    //左子樹中序遍歷結(jié)果
    $leftVin = array_slice($vin, 0, $indexInVin); 
    //右子樹先序遍歷結(jié)果
    $rightPrev = array_slice($pre, $indexInVin + 1);
    //右子樹中序遍歷結(jié)果
    $rightVin = array_slice($vin, $indexInVin + 1);
    //遞歸構(gòu)建樹
    $root->left = reConstructBinaryTree($leftPrev, $leftVin);
    $root->right = reConstructBinaryTree($rightPrev, $rightVin);
    //返回根節(jié)點
    return $root;
}

完整的代碼在這里，需要的同學(xué)可以點擊查看。

好了，我們繼續(xù)。來看第二道。

輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個樹的子結(jié)構(gòu)）

思路分析：第一種情況如果根節(jié)點相同，那么就分別去子節(jié)點里面匹配。不符合的話看
第二種情況，如果根節(jié)點不同，就去用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);
}

來看下一道。

操作給定的二叉樹，將其變換為源二叉樹的鏡像。

這個題目很有名哈，可能你也經(jīng)常看到。但是不難，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);
}

接著來看一道關(guān)于層次遍歷二叉樹的題目，除了層次遍歷之外，我們還應(yīng)當(dāng)掌握先序，中序，后續(xù)遍歷二叉樹的遞歸算法以及非遞歸算法，除此之外還有節(jié)點的搜索、新增以及刪除等常用操作都在這里了。

從上往下打印出二叉樹的每個節(jié)點，同層節(jié)點從左至右打印。

思路分析:我們需要建立一個隊列，先將根節(jié)點入隊，然后將隊首出隊，然后判斷它的左右子樹是否為空，不為空，則先將左子樹入隊，然后右子樹入隊。

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);
}

此題還有非遞歸的解法，點擊這里可以看到源代碼。

恭喜，你堅持看到這里了，真棒！我們繼續(xù)。

《劍指Offer》中還有一道類似的變種題目，就是下面的這道，之字形遍歷二叉樹。

請實現(xiàn)一個函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。

思路分析：當(dāng)我們在打印某一行的結(jié)點時，把下一層的結(jié)點保存到相應(yīng)的棧中。如果當(dāng)前打印的是奇數(shù)層，則先保存左子結(jié)點再保存右子結(jié)點到一個棧中；如果當(dāng)前打印的是偶數(shù)層，則先保存右子結(jié)點再保存左子結(jié)點到另一個棧中。

/*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;
}

好了，現(xiàn)在老鐵你可以去喝個水休息一下，因為還有不少題目等待著我們，如果累了你可以先按個贊標(biāo)記一下，明天接著看。另外源代碼點擊這里查看，老鐵也可以先star一下，以后再看，您的star是我更新的動力。

繼續(xù)

輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。

思路分析：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;
}

輸入一顆二叉樹的跟節(jié)點和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。(注意: 在返回值的list中，數(shù)組長度大的數(shù)組靠前)

思路分析：利用遞歸遍歷所有路徑。

/*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;
        }
    }
}

輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向。

思路分析：方法一：遞歸版

1.將左子樹構(gòu)造成雙鏈表，并返回鏈表頭節(jié)點。

2.定位至左子樹雙鏈表最后一個節(jié)點。

3.如果左子樹鏈表不為空的話，將當(dāng)前root追加到左子樹鏈表。

4.將右子樹構(gòu)造成雙鏈表，并返回鏈表頭節(jié)點。

5.如果右子樹鏈表不為空的話，將該鏈表追加到root節(jié)點之后。

6.根據(jù)左子樹鏈表是否為空確定返回的節(jié)點。

function Convert($pRootOfTree)
{
    // write code here
    if (empty($pRootOfTree)) {
        return null;
    }
    if (empty($pRootOfTree->left) && empty($pRootOfTree->right)) {
        return $pRootOfTree;
    }
    //將左子樹構(gòu)造成雙鏈表，并返回鏈表頭節(jié)點。
    $left = Convert($pRootOfTree->left);
    $temp = $left;
    // 2.定位至左子樹雙鏈表最后一個節(jié)點。
    while($temp !== null && $temp->right != null) {
        $temp = $temp->right;
    }
    // 3.如果左子樹鏈表不為空的話，將當(dāng)前root追加到左子樹鏈表。
    if ($left != null) {
        $temp->right = $pRootOfTree;
        $pRootOfTree->left = $temp;
    }
    // 4.將右子樹構(gòu)造成雙鏈表，并返回鏈表頭節(jié)點。
    $right = Convert($pRootOfTree->right);
    // 5.如果右子樹鏈表不為空的話，將該鏈表追加到root節(jié)點之后。
    if ($right != null) {
        $right->left = $pRootOfTree;
        $pRootOfTree->right = $right;
    }
    return $left != null ? $left : $pRootOfTree;
}

非遞歸算法
解題思路：

1.核心是中序遍歷的非遞歸算法(對的，就是上文提到的那個中序遍歷算法)。

2.修改當(dāng)前遍歷節(jié)點與前一遍歷節(jié)點的指針指向。

function ConvertNotRecursive($pRootOfTree)
{
    if (empty($pRootOfTree)) {
        return null;
    }
    $stack = new SplStack();
    $p = $pRootOfTree;
    // 用于保存中序遍歷序列的上一節(jié)點
    $pre = null;
    $isFirst = true;
    
    while ($p || !$stack->isEmpty()) {
        while($p) {
            $stack->push($p);
            $p = $p->left;
        }
        $p = $stack->pop();
        if ($isFirst) {
            // 將中序遍歷序列中的第一個節(jié)點記為root
            $pRootOfTree = $p;
            $pre = $pRootOfTree;
            $isFirst = false;
        } else {
            $pre->right = $p;
            $p->left = $pre;
            $pre = $p;
        }
        $p = $p->right;
    }
    return $pRootOfTree;
}

輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。

思路分析：最直接的做法，遍歷每個結(jié)點，借助一個獲取樹深度的遞歸函數(shù)，根據(jù)該結(jié)點的左右子樹高度差判斷是否平衡，然后遞歸地對左右子樹進(jìn)行判斷。

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));
}

給定一個二叉樹和其中的一個結(jié)點，請找出中序遍歷順序的下一個結(jié)點并且返回。注意，樹中的結(jié)點不僅包含左右子結(jié)點，同時包含指向父結(jié)點的指針。

思路分析：二叉樹的下一個節(jié)點，一共有以下情況：

1.二叉樹為空，則返回空；

2.節(jié)點右孩子存在，則設(shè)置一個指針從該節(jié)點的右孩子出發(fā)，一直沿著指向左子結(jié)點的指針找到的葉子節(jié)點即為下一個節(jié)點；

3.節(jié)點不是根節(jié)點。如果該節(jié)點是其父節(jié)點的左孩子，則返回父節(jié)點；否則繼續(xù)向上遍歷其父節(jié)點的父節(jié)點，重復(fù)之前的判斷，返回結(jié)果。

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;
}

請實現(xiàn)一個函數(shù)，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。

思路分析：首先根節(jié)點以及其左右子樹，左子樹的左子樹和右子樹的右子樹相同，左子樹的右子樹和右子樹的左子樹相同即可，采用遞歸。非遞歸也可，采用棧或隊列存取各級子樹根節(jié)點。

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);
}

可以看到遞歸的強(qiáng)大，合適運用的時候真的是事半功倍。最后下面的兩道題目分別運用了二叉樹先序、中序遍歷算法。

請實現(xiàn)兩個函數(shù)，分別用來序列化和反序列化二叉樹

/*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小的結(jié)點。例如，（5，3，7，2，4，6，8）中，按結(jié)點數(shù)值大小順序第三小結(jié)點的值為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;
}

完整內(nèi)容

PHP基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)專題系列目錄地址：地址主要使用PHP語法總結(jié)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法。還有我們?nèi)粘HP開發(fā)中容易忽略的基礎(chǔ)知識和現(xiàn)代PHP開發(fā)中關(guān)于規(guī)范、部署、優(yōu)化的一些實戰(zhàn)性建議，同時還有對Javascript語言特點的深入研究。

云服務(wù)器 GPU云服務(wù)器二叉樹 python二叉樹平衡二叉樹實現(xiàn)二叉樹

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/29175.html

發(fā)表評論

登陸后可評論

0條評論

li21

男|高級講師

我要關(guān)注我要私信

TA的文章

有關(guān)hc-12的使用經(jīng)驗

閱讀 3228·2021-11-15 11:37
傲游主機(jī)(aoyoyun)，全新荷蘭/美國聯(lián)通CU2 VPS(AS10099+AS9929)

閱讀 2449·2021-09-29 09:48
機(jī)箱和主機(jī)有什么區(qū)別-迷你主機(jī)和臺式主機(jī)有什么區(qū)別？

閱讀 3813·2021-09-22 15:55
用一根網(wǎng)線連接電腦和Manifold（樹莓派）

閱讀 3014·2021-09-22 10:02
CloudCone：控制臺域名恢復(fù)正常訪問，附便宜VPS促銷方案，$12.95/年起

閱讀 2636·2021-08-25 09:40
HostMem：1核/512M/10G SSD/500G流量/1Gbps/洛杉磯CN2 GT/年付$

閱讀 3225·2021-08-03 14:03
如何用 js 獲取虛擬鍵盤高度？（適用所有平臺）

閱讀 1691·2019-08-29 13:11
CSS規(guī)范--BEM入門

閱讀 1570·2019-08-29 12:49

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

PHPer面試必看：分門別類帶你擼《劍指Offer》之二叉樹

相關(guān)文章

LeetCode 精選TOP面試題【51 ~ 100】

**劍指Offer(Java版) 持續(xù)更新中**

**【劍指offer】5.二叉樹的鏡像和打印**

發(fā)表評論

0條評論

li21

男|高級講師

TA的文章

有關(guān)hc-12的使用經(jīng)驗

傲游主機(jī)(aoyoyun)，全新荷蘭/美國聯(lián)通CU2 VPS(AS10099+AS9929)

機(jī)箱和主機(jī)有什么區(qū)別-迷你主機(jī)和臺式主機(jī)有什么區(qū)別？

用一根網(wǎng)線連接電腦和Manifold（樹莓派）

CloudCone：控制臺域名恢復(fù)正常訪問，附便宜VPS促銷方案，$12.95/年起

HostMem：1核/512M/10G SSD/500G流量/1Gbps/洛杉磯CN2 GT/年付$

如何用 js 獲取虛擬鍵盤高度？（適用所有平臺）

CSS規(guī)范--BEM入門

最新活動