程序員面試題精選100題(50)-樹的子結構[數據結構]

時間:2019-09-22 編輯:范文亭

題目:二叉樹的結點定義如下:

struct TreeNode

{

        int m_nValue;

        TreeNode* m_pLeft;

        TreeNode* m_pRight;

};

輸入兩棵二叉樹AB,判斷樹B是不是A的子結構。

例如,下圖中的兩棵樹AB,由于A中有一部分子樹的結構和B是一樣的,因此B就是A的子結構。

 

                 1                                                   8
               /    \                                               /    \
              8    7                                             9    2
            /    \
           9    2
                /  \
               4  7

分析:這是2010年微軟校園招聘時的一道題目。二叉樹一直是微軟面試題中經常出現的數據結構。對微軟有興趣的讀者一定要重點關注二叉樹。

                回到這個題目的本身。要查找樹A中是否存在和樹B結構一樣的子樹,我們可以分為兩步:第一步在樹A中找到和B的根結點的值一樣的結點N,第二步再判斷樹A中以N為根結點的子樹是不是包括和樹B一樣的結構。

本文已影響
相關文章
大亨pk10计划苹果版