手撕二叉樹

 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };

與二叉樹相關(guān)的代碼有大量的指針操作，在每次使用指針的時(shí)候，需要判斷指針是否是nullptr，以及該如何處理。

【面試題06：重建二叉樹】

題目：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。
思路：根據(jù)前序找到根節(jié)點(diǎn)，然后在中序中找到左右根序列，遞歸。采用vector裝序列，即每次遞歸更新前序vector和中序vector。如果是python，可利用list的切片。

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.empty() || vin.empty()) return nullptr; 
        vector<int>left_pre,left_vin,right_vin,right_pre;
        int rootValue = pre[0];
        //創(chuàng)建根節(jié)點(diǎn)
        TreeNode* root = new TreeNode(rootValue);
        int m = 0;
        while(m+1<vin.size() && vin[m] != rootValue){
            left_pre.push_back(pre[m+1]);
            left_vin.push_back(vin[m]);
            m++;
        } //更新左子樹的前序、中序。
        while(m+1<vin.size()){
            right_pre.push_back(pre[m+1]);
            right_vin.push_back(vin[m+1]); 
            m++;
        }//更新右子樹的前序和中序
        //重建左子樹
        root->left = reConstructBinaryTree(left_pre,left_vin);
        //重建右子樹
        root->right = reConstructBinaryTree( right_pre,right_vin);
        //返回重建二叉樹
        return root; 
    }
};
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回構(gòu)造的TreeNode根節(jié)點(diǎn)
    def reConstructBinaryTree(self, pre, tin):
        if len(pre) == 0 or len(tin) == 0:
            return None 
        root = TreeNode(pre[0])
        m = 0
        #找到中序中根節(jié)點(diǎn)的位置m
        while tin[m] != pre[0]:
            m += 1
            ##利用list的切片，直接更新左右子樹前序、中序
        root.left = self.reConstructBinaryTree(pre[1:m+1],tin[:m])
        root.right = self.reConstructBinaryTree(pre[m+1:],tin[m+1:])
        return root

【面試題58：二叉樹的下一個(gè)結(jié)點(diǎn)】

題目：給定一個(gè)二叉樹和其中的一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回。注意，樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)，同時(shí)包含指向父結(jié)點(diǎn)的指針。
思路：分兩種情況：1）節(jié)點(diǎn)存在右子樹；2）不存在右子樹，又分兩種：a)遍歷父節(jié)點(diǎn)，能找到父節(jié)點(diǎn)的左子節(jié)點(diǎn)是本身的節(jié)點(diǎn)；b)不存在a)中節(jié)點(diǎn)。

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    { 
        if(pNode == nullptr) return nullptr;
        TreeLinkNode* pNext = nullptr;
        if(pNode->right != nullptr){
            pNext = pNode->right;
            while(pNext->left != nullptr)
                pNext = pNext->left;  
        }//情況一：結(jié)點(diǎn)存在右子樹
        else if(pNode->next != nullptr){
            TreeLinkNode* pParent = pNode;
            //情況二：結(jié)點(diǎn)不存在右子樹，并不是根節(jié)點(diǎn)。
            //同時(shí)尋找父節(jié)點(diǎn)的左結(jié)點(diǎn)是本身的結(jié)點(diǎn)。
            while(pParent->next != nullptr 
                  && pParent->next->left != pParent)
                pParent = pParent->next;
            //協(xié)議節(jié)點(diǎn)為該節(jié)點(diǎn)的父節(jié)點(diǎn)，如不存在即為根節(jié)點(diǎn)的父節(jié)點(diǎn)nullptr
            pNext = pParent->next;
        }
        return pNext; 
    }
};

【面試題19：樹的子結(jié)構(gòu)】Subtree of Another Tree

題目：輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）。注意題目子結(jié)構(gòu)的定義：1）存在即可；2）存在即左右子樹全部一樣。
思路：兩步：1）找到相同根節(jié)點(diǎn)，然后遞歸判斷左右子樹，返回結(jié)果；2）遞歸左右子樹找到下一個(gè)相同根節(jié)點(diǎn)。

####子結(jié)構(gòu)定義：
     3
    / \
   4   5
  / \
 1   2
    /
   0
Given tree t:
   4
  / \
 1   2
Return false.
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(s == nullptr || t == nullptr) return false;
        bool result = false;
        if(s->val == t->val)
            result = JudgeSubTree(s,t);
        if(!result)
            result = isSubtree(s->left, t);
        if(!result)
            result = isSubtree(s->right, t);
        return result; 
    }

    bool JudgeSubTree(TreeNode* s, TreeNode* t) {
        if(s == nullptr && t == nullptr) return true;
        if(t == nullptr || s == nullptr) return false;
        if(s->val != t->val) return false;
        return JudgeSubTree(s->left,t->left) && JudgeSubTree(s->right, t->right);
        
    }
};

【面試題19：二叉樹的鏡像】

題目：完成一個(gè)函數(shù)，輸入一個(gè)二叉樹，該函數(shù)輸出它的鏡像。
思路：左右子樹交換。

class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot == nullptr) return;
        if(pRoot->left == nullptr && pRoot->right == nullptr)
            return ;
        TreeNode* temp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = temp;
        
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
};

【面試題59：對(duì)稱的二叉樹】

題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)來判斷一棵二叉樹是不是對(duì)稱的。如果一棵二叉樹和它的鏡像一樣，那么它是對(duì)稱的。
思路：1）求出二叉樹的鏡像，然后判斷是否與原二叉樹相等。具體：將根節(jié)點(diǎn)的左子樹鏡像，然后與右子樹相比。
2）采用遍歷思想，對(duì)稱即左和右可以交換，以前序遍歷為例，根左右和根右左應(yīng)該是相等的。

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        return isSymmetricalTree(pRoot,pRoot);
    }
    bool isSymmetricalTree(TreeNode* pRoot1,TreeNode* pRoot2){
        if(pRoot1 == nullptr && pRoot2 == nullptr)
            return true;
        if(pRoot1 == nullptr || pRoot2 == nullptr)
            return false;
        if(pRoot1->val != pRoot2->val)
            return false;
        return isSymmetricalTree(pRoot1->left, pRoot2->right)
            && isSymmetricalTree(pRoot1->right, pRoot2->left);
    } 
};

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
         if(root == nullptr || (root->left ==nullptr && root->right == nullptr))
            return true;
        TreeNode* leftTree = Mirror(root->left);
        return isSameTree(leftTree, root->right); 
    }
    ###遞歸代碼的理解，如函數(shù)需要返回根節(jié)點(diǎn)：
    TreeNode* Mirror(TreeNode* pRoot){
        if(pRoot == nullptr)
            return nullptr;
        if(pRoot->left == nullptr && pRoot->right == nullptr)
            return pRoot;
        TreeNode* temp = pRoot->left; 
        
        pRoot->left = Mirror(pRoot->right);
        pRoot->right = Mirror(temp);
        return pRoot;
    }
    
    bool isSameTree(TreeNode* t1, TreeNode* t2){
        if(t1 == nullptr && t2 == nullptr)
            return true;
        if(t1 == nullptr || t2 == nullptr) return false;
        if(t1->val != t2->val)
            return false;
        return isSameTree(t1->left, t2->left) && isSameTree(t1->right, t2->right);
    }
    
};

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

題目：從上往下打印出二叉樹的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。
思路：利用隊(duì)列前出后進(jìn)操作，逐層遍歷push進(jìn)隊(duì)列。

class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        if(root == nullptr) return {};
        vector<int>result;
        deque<TreeNode*>dequeOrder;
        dequeOrder.push_back(root);
        while(dequeOrder.size()){
            TreeNode *curNode = dequeOrder.front();
            result.push_back(curNode->val);
            dequeOrder.pop_front();
            if(curNode->left)
                dequeOrder.push_back(curNode->left);
            if(curNode->right)
                dequeOrder.push_back(curNode->right);
        }
        return result;
    }
};

【面試題24：二叉搜索樹的后序遍歷序列】

題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。
思路：找出根節(jié)點(diǎn)，然后遍歷序列，找到左右子樹，然后遞歸，不滿足條件即返回false。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        int root = sequence[sequence.size()-1];
        int i = 0;
        vector<int> left,right;
        while(i<sequence.size()-1 && sequence[i]<root)
            left.push_back(sequence[i++]);  
        while(i<sequence.size()-1 && sequence[i]>root)
            right.push_back(sequence[i++]);
        if(i != sequence.size()-1) return false;
        bool isLeft = true, isRight = true;
        if(!left.empty())
            isLeft = VerifySquenceOfBST(left);
        if(!right.empty())
            isRight = VerifySquenceOfBST(right);
        return  isLeft && isRight;
    }
};

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

題目：輸入一顆二叉樹的跟節(jié)點(diǎn)和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。
思路：遍歷二叉樹，采用前序，即先訪問根節(jié)點(diǎn)進(jìn)行操作，然后遞歸左右子樹。具體來說：訪問當(dāng)前節(jié)點(diǎn)若為葉節(jié)點(diǎn)且滿足和相等，則打印或push_back，然后遞歸左右子樹。不管怎么樣到達(dá)葉節(jié)點(diǎn)，需要pop_back，返回父節(jié)點(diǎn)。

class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>>pathAll;
        if(root == nullptr)
            return pathAll;
        vector<int>path; 
        pathFind(root,expectNumber,path,pathAll,0);
        return pathAll;
    } 
    
    void pathFind(TreeNode* root, int sum, vector<int>path, 
                                 vector<vector<int>> &pathAll, int curSum){
        if(root == nullptr) return ;
        curSum += root->val; 
        path.push_back(root->val); 
        if(curSum == sum && root->left == nullptr && root->right == nullptr)
            pathAll.push_back(path);

        pathFind(root->left,sum,path,pathAll,curSum); 
        pathFind(root->right,sum,path,pathAll,curSum);
        path.pop_back(); 
    }
};

【面試題27：二叉搜索樹與雙向鏈表】

題目：輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向。
思路：由于是二叉搜索樹，其中序遍歷即為最后鏈表排序順序，然后剩下來的工作就是指針的轉(zhuǎn)換操作。定義一個(gè)指針指向已經(jīng)轉(zhuǎn)好的鏈表的最后一個(gè)節(jié)點(diǎn)。當(dāng)前節(jié)點(diǎn)left指向定義節(jié)點(diǎn)，定義節(jié)點(diǎn)right指向當(dāng)前節(jié)點(diǎn)，然后定義節(jié)點(diǎn)更新成當(dāng)前節(jié)點(diǎn)。

/*
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)
    {
        ConvertNode(pRootOfTree);
        TreeNode* pHead = pNode;
        while(pHead != nullptr && pHead->left != nullptr)
            pHead = pHead->left;
        return pHead;
    }
    
    void ConvertNode(TreeNode* pRoot){
        if(pRoot != nullptr){ 
            //訪問左子樹
            ConvertNode(pRoot->left);
            //訪問節(jié)點(diǎn)pRoot，為中序遍歷節(jié)點(diǎn)，進(jìn)行指針操作。
            pRoot->left = pNode;
            if(pNode != nullptr)
                pNode->right =  pRoot;
            pNode =  pRoot;
            //訪問右子樹
            ConvertNode(pRoot->right); 
        }
    }
private:
    TreeNode* pNode = nullptr;
};

【面試題60：把二叉樹打印出多行】

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

【面試題62：序列化二叉樹】

【面試題63：二叉搜索樹的第k個(gè)結(jié)點(diǎn)】

題目：給定一棵二叉搜索樹，請(qǐng)找出其中的第k小的結(jié)點(diǎn)。例如， （5，3，7，2，4，6，8） 中，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為4。
思路：中序遍歷，如果滿足k == 1 則返回此時(shí)節(jié)點(diǎn)。

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    { 
        TreeNode* kthNode = nullptr;
        InOrder(pRoot,k,&kthNode);   
        return kthNode;
    }
    
    void InOrder(TreeNode* pRoot, int &k, TreeNode** kthNode){
        if(pRoot != nullptr){ 
            InOrder(pRoot->left, k, kthNode);
            if(k-- == 1){
                *kthNode = pRoot; 
                return ;
            }
            InOrder(pRoot->right, k, kthNode);
        } 
    } 
};
//帶返回值的遞歸
class Solution {
    int count = 0; //引入成員變量,如果k是值傳遞的話。
public:
    TreeNode* KthNode(TreeNode* pRoot, unsigned int &k)
    {//k為引用傳遞
        if(pRoot){ 
                TreeNode *ret = KthNode(pRoot->left, k);
                if(ret) return ret; // 左子樹找的到第k個(gè)，則temp不為nullptr，返回temp
                if(--k == 0) return pRoot; // 如果滿足條件，返回proot（不為nullptr）
                ret = KthNode(pRoot->right,k);
                if(ret) return ret;//同理
        }//如果找不到，則一直遍歷，最后返回nullptr。
        return nullptr;
    }
};

【面試題39：二叉樹的深度】

題目：輸入一棵二叉樹，求該樹的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹的深度。
拓展：平衡二叉樹的判斷。
思路：深度計(jì)算為左右子樹去較大值+1，進(jìn)而遞歸左右子樹累加深度。判斷平衡二叉樹，不僅需要計(jì)算左右子樹的深度，而且還要判斷是否平衡，返回bool。進(jìn)而增加一個(gè)引用，用于計(jì)算深度，函數(shù)返回是否平衡。
啟發(fā)：一個(gè)函數(shù)存在多個(gè)變量需要返回時(shí)，可以增加函數(shù)參數(shù)（采用引用傳遞）。

class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {//計(jì)算二叉樹深度
        if(pRoot == nullptr)
            return 0 ;
        int depthLeft = TreeDepth(pRoot->left);
        int depthRight = TreeDepth(pRoot->right);
        return depthLeft>depthRight? depthLeft+1: depthRight+1;
    }
 //判斷平衡二叉樹 
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth = 0;
        return IsBalancedTree(pRoot,depth);
    }
    bool IsBalancedTree(TreeNode* pRoot, int &depth) {
        if(pRoot == nullptr){
            depth = 0;
            return true;
        }
        int left, right;
        if(IsBalancedTree(pRoot->left,left) 
           && IsBalancedTree(pRoot->right,right)){
            int diff = left -right;
            if(diff<=1 && diff>=-1){
                depth = left > right ? left+1 : right+1;
                return true;
            }
        }
        return false;
    }
};
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容