樹

記錄《劍指offer》中所有關于樹的題目匿又，以及LeetCode中的相似題目方灾。

相關題目列表

題目

樹是一種最常考的數據結構旭绒，尤其是二叉樹鸟妙，其中二叉樹的各種遍歷方法，以及樹的各種子結構操作挥吵，都需要靈活掌握重父。

面試題6： 重建二叉樹

題目： 輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹忽匈。假設輸入的前序遍歷和中序遍歷的結果中都不包含重復的數字房午。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建出如下圖的二叉樹丹允，并輸出它的頭結點郭厌。

重構二叉樹

題目分析

根據二叉樹的前序遍歷與中序遍歷序列的特定，可以判斷節(jié)點直接的相對位置雕蔽，從而得出重構二叉樹折柠。
具體的做法是，根據前序遍歷得知根結點批狐，然后根據中序遍歷將序列分成左右子樹扇售，從而遞歸完成二叉樹的重構。

參考代碼

#include<iostream>
#include<vector>

using namespace std;


struct BinaryTreeNode
{
    int val;
    BinaryTreeNode* left;
    BinaryTreeNode* right;

    BinaryTreeNode(int x) : val(x), left(NULL), right(NULL) {}

    //輸出前序遍歷結果
    static void PreOrder(BinaryTreeNode* root)
    {
        if (root == NULL)
        {
            return;
        }
        cout << root->val << " ";
        PreOrder(root->left);
        PreOrder(root->right);
    }

    //輸出中序遍歷結果嚣艇，采用static
    static void InOrder(BinaryTreeNode* root)
    {
        if (root == NULL)
        {
            return;
        }
        InOrder(root->left);
        cout << root->val << " ";
        InOrder(root->right);
    }

    //輸出后序遍歷結果
    static void LatOrder(BinaryTreeNode* root)
    {
        if (root == NULL)
        {
            return;
        }
        LatOrder(root->left);
        LatOrder(root->right);
        cout << root->val << " ";
    }
};

class Solution
{
public:
    BinaryTreeNode* reConstructBinaryTree(vector<int> pre, vector<int> in)
    {
        //前序遍歷的長度和中序遍歷相同
        if (pre.size() != in.size())
        {
            return NULL;
        }

        //長度不能為0
        int length = pre.size();
        if (length == 0)
        {
            return NULL;
        }

        //int length = pre.size();

        int value = pre[0];     //前序遍歷的第一個結點是根結點

        BinaryTreeNode *root = new BinaryTreeNode(value);

        //找到中序遍歷中的根結點
        int rootIndex = 0;
        for (int i = 0; i < length; ++i)
        {
            if (in[i] == value)
            {
                rootIndex = i;
                break;
            }
        }

        //區(qū)分左子樹和右子樹
        //中序遍歷中缘眶，根左邊的就是左子樹，右邊的就是右子樹
        //前序遍歷中髓废，根后面的是先遍歷左子樹，然后遍歷右子樹

        //首先確定左右子數的長度该抒，從中序遍歷in中確定

        vector<int> preLeft, inLeft, preRight, inRight;

        for (int i = 0; i < rootIndex; ++i)
        {
            //前序遍歷的第一個結點是根結點慌洪，所以是i+1
            preLeft.push_back(pre[i+1]);
            //中序遍歷的前i個結點即使中序遍歷的左子樹
            inLeft.push_back(in[i]);
        }
        for (int i = rootIndex + 1; i < length; ++i)
        {
            //前序遍歷的右子樹
            preRight.push_back(pre[i]);
            //中序遍歷的右子樹
            inRight.push_back(in[i]);
        }


        root->left = reConstructBinaryTree(preLeft, inLeft);
        root->right = reConstructBinaryTree(preRight, inRight);

        return root;
    }
};

int main()
{
    int pre[] = {1,2,4,7,3,5,6,8};
    int in[] = {4,7,2,1,5,3,8,6};

    vector<int> preOrder(pre, pre+8);
    vector<int> inOrder(in, in+8);

    Solution solu;
    BinaryTreeNode *root = solu.reConstructBinaryTree(preOrder, inOrder);

    cout << root->val << endl;

    BinaryTreeNode::PreOrder(root);
    cout << endl;
    BinaryTreeNode::InOrder(root);
    cout << endl;
    BinaryTreeNode::LatOrder(root);

    return 0;
}

相似題目

本題與LeetCode中的105. Construct Binary Tree from Preorder and Inorder Traversal
完全一致顶燕，另外LeetCode中還有一道已知中序和后續(xù)的題目106. Construct Binary Tree from Inorder and Postorder Traversal
,這兩題的參考代碼見：
LeetCode 105 code
LeetCode 106 code
還可以在牛客網 劍指offer上完成對本題的練習冈爹。

面試題18：樹的子結構

題目： 輸入兩棵二叉樹A和B涌攻，判斷B是不是A的子結構。

題目分析

要查找A中是否存在和B結構一樣的子樹频伤，可以分為兩步進行：第一步在A中找到和B的根結點的值一樣的結點R恳谎，第二步判斷樹A中以R為根結點的子樹是不是包含和樹B一樣的結構。
第一步在樹A中查找結點憋肖，這實際上就是樹的遍歷因痛，遍歷可以采用遞歸的方式完成。
第二步是判斷A中以R為根結點的子樹是不是和B有相同的結構岸更，也可以采用遞歸的方式完成鸵膏。

參考代碼

#include<iostream>
using namespace std;

struct BinaryTreeNode
{
    int val;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};

class Solution
{
public:
    //尋找到與tree2根結點相同的結點。才執(zhí)行之后的操作怎炊，若是找不到則向下遍歷谭企，知道找到再判斷左右子樹。
    bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
    {
        bool result = false;
        if (pRoots != NULL && pRoot2 != NULL)   //兩棵樹不能為空
        {
            if (pRoot1->val == pRoot2->val)     //根結點相等之后评肆，轉為比較左右子結點
                result = DoesTreeHaveTree2(pRoot1, pRoot2);
            if (!result)        //左右子節(jié)點不滿足條件债查，在tree1中重新尋找與tree2根結點相等的結點
                result = HasSubtree(pRoot1->left, pRoot2);  //在左子樹中找
            if (!result)
                result = HasSubtree(pRoot1->right, pRoot2); //在右子樹中找
        }
        return result;
    }
private:
    bool DoesTreeHaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
    {
        if (pRoot2 == NULL)     //經過查找對比，最好到了tree2的葉子節(jié)點瓜挽，則遍歷結束盹廷。返回true，這個條件必須在下一個條件之前
            return true;
        if (pRoot1 = NULL)      //若查找對比最后到了tree1的葉子節(jié)點則秸抚，證明沒有找到對應的子樹
            return false;

        if (pRoot1->val != pRoot2->val)
            return false;

        //如果根結點相等速和，則分別判斷左右子樹
        return DoesTreeHaveTree2(pRoot1->left, pRoot2->left) && DoesTreeHaveTree2(pRoot1->right, pRoot2->right);
    }
};

相似題目

本題與LeetCode中的572. Subtree of Another Tree完全一致，參考代碼見：
LeetCode 572 code
還可以在虐溃客網 劍指offer上完成對本題的練習颠放。

面試題19： 二叉樹的鏡像

題目： 請完成一個函數，輸入一個二叉樹吭敢，該函數輸出它的鏡像碰凶。

題目分析

分析題目可知，二叉樹的鏡像問題鹿驼，其實就是遞歸交換根結點的左右子樹的問題欲低。
于是，我們通過先序遍歷這棵樹的每個結點畜晰，如果該結點存在你左右子樹砾莱，就交換它的兩個子結點，當交換玩所有非葉子節(jié)點的左右子結點后凄鼻，就得到了二叉樹的鏡像腊瑟。

參考代碼

#include<iostream>

using namespace std;

struct BinaryTreeNode
{
    int val;
    BinaryTreeNode* left;
    BinaryTreeNode* right;

    BinaryTreeNode(int x): val(x), left(NULL), right(NULL) {}

    static void PreOrder(BinaryTreeNode* root)
    {
        if (root == NULL)
            return;
        cout << root->val << " ";
        PreOrder(root->left);
        PreOrder(root->right);
    }

    static void InOrder(BinaryTreeNode* root)
    {
        if (root == NULL)
            return;
        InOrder(root->left);
        cout << root->val << " ";
        InOrder(root->right);
    }

    static void LatOrder(BinaryTreeNode* root)
    {
        if (root == NULL)
            return;
        LatOrder(root->left);
        cout << root->val << " ";
        LatOrder(root->right);
    }
};

class Solution
{
public:
    void mirrorOfBinaryTree(BinaryTreeNode* pNode)
    {
        if (pNode == NULL)
            return NULL;
        if (pNode->left == NULL && pNode->right == NULL)    //μY1é?áê?ì??t
            return NULL;

        BinaryTreeNode* temp;
        temp = pNode->left;
        pNode->left = pNode->right;
        pNode->right = temp;

        if (pNode->left)
            mirrorOfBinaryTree(pNode->left);
        if (pNode->right)
            mirrorOfBinaryTree(pNode->right);
    }
};

相似題目

本題與LeetCode中的226. Invert Binary Tree一題完全一致聚假，參考代碼見：
LeetCode 226 code
還可以在牛客網 劍指offer上完成對本題的練習闰非。

面試題23： 從上往下打印二叉樹

題目： 從上往下打印二叉樹的每個結點膘格，同一層的結點按照從左往右的順序打印。

題目分析

本題是二叉樹的層序遍歷财松，使用雙向隊列完成瘪贱。

參考代碼

//二叉樹的層序遍歷
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> result;

        if (root == NULL)
            return result;

        std::deque<TreeNode*> dequeTreeNode;    //利用隊列先入先出的特性
        dequeTreeNode.push_back(root);
        while (dequeTreeNode.size()){   //如果隊列中存在元素，在彈出首元素的同時壓入這個元素對應的左右子樹
            TreeNode* pNode = dequeTreeNode.front();
            result.push_back(pNode->val);
            dequeTreeNode.pop_front();

            if (pNode->left != NULL)
                dequeTreeNode.push_back(pNode->left);
            if (pNode->right != NULL)
                dequeTreeNode.push_back(pNode->right);
        }
        return result;

    }
};

相似題目

本題與LeetCode中的102. Binary Tree Level Order Traversal
完全一致辆毡，另外LeetCode中還有一道本題的延伸107. Binary Tree Level Order Traversal II
菜秦。這兩題的參考代碼見：
LeetCode 102 code
LeetCode 107 code
還可以在牛客網 劍指offer上完成對本題的練習胚迫。

面試題24： 二叉搜索樹的后續(xù)遍歷序列

題目： 輸入一個整數數組喷户，判斷該數組是不是某二叉搜索樹的后序遍歷結果。如果是返回true访锻，否則返回false褪尝。假設輸入的數組的任意兩個數字都互不相同。

題目分析

首先期犬，二叉搜索樹要求每個結點左子樹的值都小于本結點的值河哑，所有右子樹上的值都大于本節(jié)點的值。
以數組{5,7,6,9,11,10,8}為例龟虎，后序遍歷中8為樹的根結點璃谨，所以5,7,6為8的左子樹，9,11,10為8的右子樹鲤妥，因此在8結點上滿足條件佳吞。由此可以用相同的方法判斷每個非葉子結點是否都滿足二叉搜索樹的條件。

參考代碼

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int length = sequence.size();
        if (length == 0)
            return false;

        return result(sequence, 0, length - 1);
    }

private:
    bool result(vector<int> sequence, int start, int end){
        if (start >= end)
            return true;    //遞歸結束條件

        int root = sequence[end];
        int i = start;
        while (sequence[i] < root){
            ++i;
        }

        //判斷右子樹
        int j = i;
        while (j < end){
            if (sequence[j] < root){
                return false;
            }
            ++j;
        }

        return result(sequence, start, i-1) && result(sequence, i, end-1);
    }
};

相似題目

LeetCode中有一道是驗證二叉搜索樹的前序序列棉安，但是是一道收費題255
Verify Preorder Sequence in Binary Search Tree 底扳，其實方法都是一樣的。
可以在殴钡ⅲ客網 劍指offer上對本題進行練習衷模。

面試題25： 二叉樹中和為某一值的路徑

題目： 輸入一棵二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑蒲赂。從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑阱冶。

題目分析

此題用前序遍歷的方式訪問到某一結點時，我們把該結點添加到路徑上滥嘴，并累加該結點的值木蹬。如果該結點為葉結點并且路徑中結點值的和正好等于輸入整數，則當前路徑符合若皱，打印出來届囚。如果當前結點不是葉結點有梆，則繼續(xù)訪問它的子結點。當前結點結束訪問后意系，遞歸函數將自動回到它的父結點。因此我們在函數退出之前要在路徑上刪除當前結點并減去當前結點的值饺汹，以確保返回父結點時路徑剛好是從根結點到父結點的路徑蛔添。我們不難看出，這其實就是一個棧兜辞，因為路徑要與遞歸調用狀態(tài)一致迎瞧，而遞歸調用的本質就是一個壓棧和出棧的過程。

參考代碼

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<vector<int>> res;    //將res和path設置為全局變量
    vector<int> path;
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
        find(root, expectNumber);
        return res;
    }
private:
    void find(TreeNode* root, int sum){
        if (root == NULL)
            return;
        path.push_back(root->val);
        bool isLeaf = root->left == NULL && root->right == NULL;
        if ((root->val == sum) && isLeaf){      //判斷是否滿足條件
            res.push_back(path);
        }
        else{       //如果不滿足逸吵，則遞歸
            if (root->left != NULL)
                find(root->left, sum - root->val);
            if (root->right != NULL)
                find(root->right, sum - root->val);
        }
        path.pop_back();    //在返回到父結點之前凶硅，在路徑上刪除當前節(jié)點
    }
};

相似題目

本題與LeetCode中的113. Path Sum II完全一致，另外LeetCode中還有兩道類似題目扫皱，分別是本題的簡化版本（判斷是否存在一個路徑）112. Path Sum; 以及強化版本（不設定路徑起始限制）437. Path Sum III
這三道題的參考代碼見：
LeetCode 113 code
LeetCode 112 code
LeetCode 437 code

還可以在抛闵穑客網 劍指offer上完成對本題的練習。

面試題27： 二叉樹與雙向鏈表

題目： 輸入一棵二叉搜索樹韩脑，將該二叉搜索樹轉換成一個排序的雙向鏈表氢妈。要求不能創(chuàng)建任何新的結點，只能調整樹中結點指針的指向段多。

題目分析

根據BST與排序雙向鏈表的關系首量，原先指向左子結點的指針調整為鏈表中指向前一個結點的指針，原先指向右子結點的指針調整為鏈表中指向后一個結點的指針进苍。

接下來我們考慮如何進行轉換加缘。

根據BST中序遍歷有序的特點，我們采用中序遍歷算法從小到大遍歷二叉樹的每一個結點觉啊。當遍歷到根結點時拣宏，我們把樹看成3部分（如下圖所示），值為10的結點柄延、根結點值為6的左子樹蚀浆，根結點值為14的右子樹。根據排序鏈表的定義搜吧，值為10的節(jié)點將和它的左子樹的最大一個節(jié)點相連市俊，同時與右子樹中最小節(jié)點相連。

根據中序遍歷的順序滤奈，當我們遍歷轉換到根結點時摆昧，它的左子樹已經轉換成一個排序鏈表了，并且最后一個節(jié)點即為其中最大的結點。我們把8與10相連即可药磺。接著遍歷轉換右子樹厉碟，并把根結點和右子樹中最小的結點相連棘钞。

參考代碼

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode* pLastNodeInList = NULL;
        ConverNode(pRootOfTree, &pLastNodeInList);  //因為函數形參是二重指針届谈，所以需要用取地址符

        TreeNode* pHeadOfList = pLastNodeInList;
        while (pHeadOfList != NULL && pHeadOfList->left != NULL)
            pHeadOfList = pHeadOfList->left;
        return pHeadOfList;
    }
private:
    //類似于中序遍歷
    void ConverNode(TreeNode* pNode, TreeNode** pLastNodeInList){   //因為需要對pLastNodeInList進行動態(tài)改變企巢，所以需要用二重指針
        if (pNode == NULL)
            return;

        TreeNode* pCurrent = pNode;
        if (pCurrent->left != NULL)
            ConverNode(pCurrent->left, pLastNodeInList);

        pCurrent->left = *pLastNodeInList;

        if (*pLastNodeInList != NULL)
            (*pLastNodeInList)->right = pCurrent;

        *pLastNodeInList = pCurrent;

        if (pCurrent->right != NULL)
            ConverNode(pCurrent->right, pLastNodeInList);
    }
};

相似題目

本題與LeetCode中的109. Convert Sorted List to Binary Search Tree類似哮奇，其是將單鏈表轉化為BST西壮。
還可以在排伎澹客網 劍指offer上完成對本題的練習张咳。

面試題39_1： 二叉樹的深度

題目： 輸入一棵二叉樹的根結點，求該樹的深度似舵。從根結點到葉結點一次經過的節(jié)點形成樹的一條路徑脚猾，最長路徑的長度為樹的深度。

題目分析

首先我們可以采用面試題25中的方法尋找路徑砚哗，即可得到深度龙助。
這里我們采用一種新的方法。
如果一棵二叉樹只有一個根結點蛛芥，則它的深度為1提鸟，如果只有右子樹而沒有左子樹，則其深度就是1+右子樹的深度常空，以此類推沽一，從而形成一個遞歸。

參考代碼

#include<iostream>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
};

class Solution
{
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if (pRoot == NULL)
            return 0;

        int Left = TreeDepth(pRoot->left);
        int Right = TreeDepth(pRoot->right);

        return 1+(Left >= Right) ? Left : Right;
    }
};

相似題目

本題與LeetCode中的104. Maximum Depth of Binary Tree與111. Minimum Depth of Binary Tree類似漓糙，其分別是求二叉樹的最大最小深度铣缠。參考代碼見：
LeetCode 104 code
LeetCode 111 code
還可以在牛客網 劍指offer上完成對本題的練習昆禽。

題目39_2： 判斷是否為AVL樹

題目： 輸入一棵二叉樹的根結點蝗蛙，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意節(jié)點的左右子樹的深度相差不超過1醉鳖，那么它就是一棵平衡二叉樹捡硅。

題目分析

可以根據39_1中二叉樹的深度逐結點判斷左右子樹深度差，從而確定是否是AVL樹盗棵，但是這樣做的缺點是顯而易見的壮韭，每個節(jié)點需要訪問多次。
下面采用一種新的方法：
如果我們采用后序遍歷的方式遍歷二叉樹的每一個結點纹因，在遍歷到一個結點之前喷屋，我們就已經遍歷了它的左右子樹。只要在遍歷每個結點的時候記錄它的深度瞭恰，我們就可以一邊遍歷一邊判斷每個節(jié)點是不是平衡的屯曹。

參考代碼

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
};

/*===============方法一，需要多次遍歷同一節(jié)點====================*/
class Solution
{
public:
    bool IsBalancedTree(TreeNode* pRoot)
    {
        if (pRoot == NULL)
            return true;
        int Left = TreeDepth(pRoot->left);
        int Right = TreeDepth(pRoot->right);
        int diff = Left - Right;
        if (diff > 1 || diff < -1)
            return false;

        return IsBalancedTree(pRoot->left) && IsBalancedTree(pRoot->right);
    }
private:
    int TreeDepth(TreeNode* pRoot)
    {
        if (pRoot == NULL)
            return 0;
        int Left = TreeDepth(pRoot->left);
        int Right = TreeDepth(pRoot->right);

        return (Left >= Right) ? (Left + 1) : (Right + 1);  //更新深度
    }
};

/*====================方法二，每個節(jié)點只需要遍歷一次======================*/
class Solution2
{
public:
    bool IsBalancedTree(TreeNode* pRoot)
    {
        int Depth = 0;
        return IsBalanced(pRoot, Depth);
    }
private:
    bool IsBalanced(TreeNode* pRoot, int& depth)    //必須將depth設置為引用恶耽，因為在遍歷過程中depth需要改變
    {
        if (pRoot == NULL)  //遞歸結束條件
        {
            depth = 0;
            return true;
        }
        int left = right = 0;
        if (IsBalanced(pRoot->left, left) && IsBalanced(pRoot->right, right))
        {
            int diff = left - right;
            if (diff <= 1 && diff >= -1)
            {
                depth = 1 + (left>right?left:right);    //更新depth
                return true;
            }
        }
        return false;
    }
};

相似題目

本題與LeetCode中的110. Balanced Binary Tree
完全一致密任。參考代碼見：
LeetCode 110 code
還可以在牛客網 劍指offer上完成對本題的練習偷俭。

面試題50： 樹中兩個結點的最低公共祖先

題目： 首先如果樹是二叉樹浪讳，或者是BST這就是不同的題目，首先如果是BST社搅，那由于BST的排序性驻债，只需要將這兩個結點與根結點對比，判斷兩個節(jié)點是在左右子樹中形葬，如果這兩個節(jié)點分別在左右子樹中，則根結點即為所求暮的。依次類推笙以，只需要從上到下找到這兩個結點之間的第一個結點即為所求。
如果是一棵普通二叉樹冻辩，本題最好的做法是通過兩個輔助鏈表記錄到兩個結點的路徑猖腕，從而將其轉化為求兩個鏈表的最后公共結點。

參考代碼

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    //TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL || p == NULL || q == NULL)
            return NULL;

        list<TreeNode*> path1;
        list<TreeNode*> path2;

        GetNodePath(root, p, path1);    //待會判斷真假
        GetNodePath(root, q, path2);

        return GetLastCommonNode(path1, path2);

    }
private:
    bool GetNodePath(TreeNode* root, TreeNode* pNode, list<TreeNode*> &path){   //得到節(jié)點路徑
        path.push_back(root);
        if (root == pNode)
            return true;

        bool found = false;

        if (!found && root->left != NULL)
            found = GetNodePath(root->left, pNode, path);
        if (!found && root->right != NULL)
            found = GetNodePath(root->right, pNode, path);

        if (!found)
            path.pop_back();

        return found;
    }

    TreeNode* GetLastCommonNode(list<TreeNode*> path1, list<TreeNode*> path2){  //尋找兩跳路徑上的最后一個公共節(jié)點
        list<TreeNode*>::iterator iterator1 = path1.begin();
        list<TreeNode*>::iterator iterator2 = path2.begin();

        TreeNode* pLast = NULL;
        while (iterator1 != path1.end() && iterator2 != path2.end()){
            if (*iterator1 == *iterator2)
                pLast = *iterator1;
            iterator1++;
            iterator2++;
        }
        return pLast;
    }
};

相似題目

LeetCode中235. Lowest Common Ancestor of a Binary Search Tree
一題為找到BST兩個結點的最低公共結點恨闪，236. Lowest Common Ancestor of a Binary Tree
為二叉樹尋找公共結點倘感。這兩題的參考代碼見：
LeetCode 235 code
LeetCode 236 code

面試題58： 二叉樹的下一個結點

題目： 給定一個二叉樹和其中一個結點，如何找出中序遍歷順序的下一個結點咙咽？樹中的結點除了有兩個分別指向左右子結點的指針以外老玛，還有一個指向父結點的指針。

題目分析

根據二叉樹的結構钧敞，本題中所給節(jié)點有如下幾種情況：
1蜡豹、如果一個節(jié)點有右子樹，則其下一個結點就是它右子樹中最左子結點溉苛。
2镜廉、如果沒有右子樹：
2.1 如果結點就是它父結點的左子結點，則它的下一個結點就是它的父結點愚战。
2.2 如果一個節(jié)點既沒有右子樹娇唯，并且還是它父結點的右子結點，這種情形比較復雜寂玲。我們可以沿著指向父結點的指針一直向上遍歷塔插，直到找到一個是它父結點的左子結點的節(jié)點，這個結點如果存在敢茁，則它的父結點就是我們要找的下一個結點佑淀。

參考代碼

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if (pNode == NULL)
            return NULL;
        TreeLinkNode* pRes = NULL;
        if (pNode->right != NULL){
            TreeLinkNode* pRight = pNode->right;
            while (pRight->left != NULL)
                pRight = pRight->left;
            pRes = pRight;
        }
        else{
            while (pNode->next != NULL){    //直到找到此結點是其父結點的左孩子，如果是左子樹，則直接返回伸刃，如果不是則向上找
                if (pNode->next->left == pNode)
                    return pNode->next;
                pNode = pNode->next;
            }
            pRes = pNode->next;
        }
        return pRes;
    }
};

相似題目

可以在呕牙客網 劍指offer上完成對本題的練習。

面試題59： 對稱的二叉樹

題目： 請實現(xiàn)一個函數捧颅，用來判斷一棵二叉樹是不是對稱的景图。

題目分析

可以通過這個二叉樹的前序遍歷與對稱前序遍歷是否相同來判斷是否是對稱二叉樹。

參考代碼

struct TreeNode
{
    int val;
    struct TreeNode* right;
    struct TreeNode* left;
};

class Solution
{
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        return isSymmetrical(pRoot, pRoot);
    }
private:
    bool isSymmetrical(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if (pRoot1 == NULL && pRoot2 == NULL)   //兩個同時為NULL
            return true;
        if (pRoot1 == NULL || pRoot2 == NULL)   //如果只有一個先到達NULL
            return false;
        if (pRoot1->val != pRoot2->val)     //一旦不相等
            return false;

        return isSymmetrical(pRoot1->left, pRoot2->right) && isSymmetrical(pRoot1->right, pRoot2->left);
    }

};

相似題目

本題與LeetCode中的101. Symmetric Tree完全一致碉哑，參考代碼見：
LeetCode 101 code
還可以在胖勘遥客網 劍指offer上完成對本題的練習。

面試題60：把二叉樹打印成多行

題目： 從上到下按層打印二叉樹扣典，同一層的結點按從左到右的順序打印妆毕，每一層打印到一行。

題目分析

本題與23題層序打印類似贮尖，可以使用雙向隊列來保存將要打印的結點笛粘。

參考代碼

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int> > Print(TreeNode* pRoot) {
        if (pRoot == NULL)
            return res;
        std::queue<TreeNode*> nodes;
        nodes.push(pRoot);
        while (!nodes.empty()){
            vector<int> temp;
            int size = nodes.size();
            for (int i = 0; i < size; ++i){
                TreeNode* pNode = nodes.front();
                temp.push_back(pNode->val);
                nodes.pop();

                if (pNode->left != NULL) nodes.push(pNode->left);
                if (pNode->right != NULL) nodes.push(pNode->right);
            }
            res.push_back(temp);
        }
        return res;
    }
};

相似題目

可以在牛客網 劍指offer上完成對本題的練習湿硝。

面試題61： 按之字形順序打印二叉樹

題目： 請實現(xiàn)一個函數薪前，按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印关斜，第二層按照從右到左的順序打印示括，第三行再按照從左到右的順序打印，其他行以此類推痢畜。

題目分析

本題與上一題一樣都是二叉樹的層序遍歷的變型題垛膝，本題與傳統(tǒng)層序遍歷的區(qū)別在于，只需要維護一個變量裁着，這個變量的作用是判斷本行是從左往右還是從右向左繁涂。

參考代碼

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
};

class Solution
{
public:
    vector<vector<int>> res;
    vector<vector<int>> Print(TreeNode* pRoot)
    {
        if (pRoot == NULL)
            return res;
        std::queue<TreeNode*> nodes;
        nodes.push(pRoot);
        bool even = false;  //判斷奇偶層，看是否需要reverse
        while (!nodes.empty())
        {
            vector<int> temp;
            int size = nodes.size();
            for (int i = 0; i < size; ++i)
            {
                TreeNode* pNode = nodes.front();
                temp.push_back(pNode->val);
                nodes.pop();

                if (pNode->left != NULL) nodes.push(pNode->left);
                if (pNode->right != NULL) nodes.push(pNode->right);
            }
            if (even)
                std::reverse(temp.begin(), temp.end());
            even = !even;
            res.push_back(temp);
        }
        return res;
    }
};

相似題目

本題與LeetCode中103. Binary Tree Zigzag Level Order Traversal完全一致二驰，參考代碼見：
LeetCode 103 code
還可以在湃幼铮客網 劍指offer上完成對本題的練習。

面試題62： 序列化二叉樹

題目： 請事先兩個函數桶雀，分別用來序列化和反序列化二叉樹矿酵。

題目分析

本題采用流的方式完成對二叉樹的序列化與反序列化。

參考代碼

void Serialize(treeNode* root, ostream& stream) {
    if (root == nullptr) {
        stream << "#,";
        return;
    }
    stream << "root->val" << ",";
    Serialize(root->left, stream);
    Serialize(root->right, stream);
}

void Deserialize(treeNode** root, istream& stream) {
    int number;
    if (ReadStream(stream, &number)) {
        *root = new treeNode();
        (*root)->val = number;
        (*root)->left = nullptr;
        (*root)->right = nullptr;
        
        Deserialize( &((*root)->left), stream);
        Deserialize( &((*root)->right), stream);
    }
}

相似題目

可以在糯；客網 劍指offer上完成對本題的練習全肮。

面試題63： 二叉搜索樹的第k個結點

題目： 給定一棵二叉搜索樹，請找出其中的第k大的節(jié)點棘捣。

題目分析

如果以中序遍歷的方式遍歷一棵BST辜腺，則中序遍歷的順序就是遞增的，于是我們只需要用中序遍歷算法遍歷一棵BST，就很容易找出它的第k大的結點评疗。

參考代碼

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if (pRoot == NULL || k == 0)
            return NULL;
        else
            return KthNodeCore(pRoot, k);
    }
private:
    //中序遍歷的第k個結點為所求,中序遍歷的時候我們在遞歸完左子樹之后打印根結點测砂，
    //本題不是打印，如果左子結點不是要找的結點百匆，才會訪問根結點砌些，所以訪問到根結點的時候要將k-1
    //因為左子結點已經證明不是要找的結點了，排除左子結點加匈。這個過程可以看成目標移位的過程存璃，
    //每經過一個結點，k-1雕拼，知道k==1纵东，當前節(jié)點就是要求的結點。
    TreeNode* KthNodeCore(TreeNode* pRoot, int& k){
        TreeNode* target = NULL;
        if (pRoot->left) target = KthNodeCore(pRoot->left, k);
        if (target == NULL){
            if (k == 1)
                target = pRoot;
            k--;
        }
        if (target == NULL && pRoot->right)
            target = KthNodeCore(pRoot->right, k);

        return target;
    }

};

相似題目

本題與LeetCode中的230. Kth Smallest Element in a BST
完全一致啥寇。參考代碼見：
LeetCode 230 code
還可以在爬河客網 劍指offer上完成對本題的練習。

【參考】
[1] 《劍指offer》
歡迎轉載示姿，轉載請注明出處： wenmingxing 《劍指offer》樹專題