二叉樹面試題

求二叉樹的高度

判斷一棵樹是否為平衡二叉樹

求二叉樹葉子節點的個數

求二叉樹第k層節點的個數

判斷某個節點是否存在于二叉樹中

求二叉樹的鏡像

求二叉樹中最遠的兩個節點之間的距離

由前序周遊和中序周遊重建二叉樹

二叉樹的高度

題目：輸入一棵二叉樹的根結點，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。

思路： 1、如果樹為空，傳回0

2、若果二叉樹隻有一個節點，傳回1

3、如果二叉樹中有左子樹，傳回左子樹的高度+1

4、如果二叉樹中有右子樹，傳回右子樹的高度+1

5、如果左右子樹都存在，則傳回高度較大的子樹值+1

代碼實作如下（遞歸思想）：

樹的節點結構：

struct BTNode
{
    BTNode(const T& data=T())//定義結構體  并初始化
    :_data(data)
    , _left(NULL)
    , _right(NULL)
    {}
    BTNode* _left;
    BTNode* _right;
    T _data;
};

size_t _Depth(Node* _root)//  左右子樹高的+1依次遞歸
    {
        if (_root == NULL)
        {
            return 0;
        }
        if (_root)
        {
        //int left=_Depth(_root->_left)
        //int right=_Depth(_root->_right) 
        //return left>right?left+1：right+1
        return (_Depth(_root->_left) > _Depth(_root->_right) 
                ? _Depth(_root->_left) : _Depth(_root->_right)) + 1;
        }
    }

判斷一棵樹是否為平衡二叉樹

題目：輸入一棵二叉樹的根結點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結點的左右子樹的深度相差不超過1，那麼它就是一棵平衡二叉樹。例如，下圖中的二叉樹就是一棵平衡二叉樹。

思路：

1、由于在上一個題中已經可以得到了樹的高度，是以隻需要求得左右子樹的高度差就可以了

2、兩顆子樹也要平衡

bool Isbalance(Node* _root)
    {
        if (_root == NULL)
            return NULL;
        int left_height = _Depth(_root->_left);
        int right_height = _Depth(_root->_right);
        int sub_height = abs(left_height - right_height);
        if (sub_height > 1)
        return false;
        //判斷兩顆子樹是否平衡
        return Isbalance(_root->_left) && Isbalance(_root->_right);
    }

但是，上面的“先序周遊”判斷二叉樹平衡的方法，時間複雜度比較大。因為，二叉樹中的很多結點周遊了多次。

比如，求解根的的高度時，需要先求解根的左子樹高度和右子樹高度，這就周遊了整棵左子樹中的結點和右子樹中的結點。而求解以根的左孩子為根的子樹的高度時，又需要周遊它(根的左孩子)的左子樹和右子樹。這樣，相當于很多結點的高度重複計算了。

根本原因是采用了“先序周遊”，求根的高度，需要先知道根的左右孩子的高度。

如果采用後序周遊，先知道某結點左右子樹的高度，如果左右子樹的高度都不滿足平衡二叉樹(二者高度相減大于1)，那麼都不需要再去求解該結點的高度了。

因為，平衡二叉樹要求二叉樹中任意結點的左右子樹高度相差不超過1

代碼實作如下：

bool isBalance(TreeNode *root, int &height)
    {
        if (root == NULL)
        {
            height = 0;
            return true;
        }

        int leftHeight = 0, rightHeight = 0;
        bool leftRet = isBalance3(root->left, leftHeight);
        bool rightRet = isBalance3(root->right, rightHeight);

        height = max(leftHeight, rightHeight) + 1;
        if (abs(leftHeight - rightHeight) > 1)
            return false;
        return leftRet && rightRet;
    }
};

二叉樹葉子節點的個數

題目：輸入一棵二叉樹的根結點，求該樹的葉子節點的個數。

思路： 1、當樹為空時，傳回0；

2、當樹隻有根節點時，傳回1

3、當樹的左右子樹都為空時，樹的葉子節點為左右子樹的葉子節點之和

代碼實作如下：

size_t _LeafSize( const Node* _root)//傳回二叉樹中葉子節點的個數 三種情況都要分别考慮到
    {
        if (_root == NULL)
        {
            return 0;
        }
        if ((_root->_left == NULL) && (_root->_right==NULL))
        {
            return 1;
        }
        if (_root)
        {
            return _LeafSize(_root->_left) + _LeafSize(_root->_right);
        }
    }

第K層節點的個數

題目：給定一個二叉樹的根節點，求二叉樹第K層節點的個數

思路： 1、如果樹為空或者K<0，傳回0

2、如果樹不為空，并且求的是樹的第一層的節點個數，傳回1

3、樹的左右子樹都不為空，傳回第k-1層左右子樹節點的個數之和

遞歸方法

size_t _GetKLevel_NodeSzie( Node* _root,int k)//傳回第k層節點的個數
    {
        if (_root == NULL||K<=0)
        {
            return 0;
        }
        if (_root!=NULL&&k==1)
        {
            return 1;
        }
        return _GetKLevel_NodeSzie(_root->_left, k - 1)
            + _GetKLevel_NodeSzie(_root->_right, k - 1);
    }

判斷一個節點是否在一顆二叉樹中

題目：給一個二叉樹的根節點，和另外一個節點，判斷此節點是否在二叉樹中

思路：

1、如果樹為空或者所給節點為空，傳回false

2、如果所給節點的值，與樹中某一個節點的值相等，傳回true

3、如果樹不為空，所給節點也不為空，依次周遊樹的左子樹和右子樹

代碼實作如下：

//判斷一個二叉樹的節點是否在二叉樹中
  bool IsNodeIntree(Node* _root, Node *node)
    {
        if (_root == NULL || node == NULL)
            return false;
        if (_root->_data == node->_data)
            return true;
        if (IsNodeIntree(_root->_left, node) || IsNodeIntree(_root->_right, node))
            return true;
        return false;
     }

求二叉樹的鏡像

題目：輸入一顆二叉樹，輸出它的鏡像

思路：

樹的鏡像就是将樹的所有左右節點全部進行交換

1、當樹為空時，直接傳回

2、當樹隻有一個節點時，直接傳回

3、當樹的左右節點都不為空時，依次交換樹的左右節點

方法1：遞歸法

void Mirrorcursively(Node *_root)
     {
         if (_root == NULL || (_root->_left == NULL&&_root->_right == NULL))
             return;
         Node *ptmp = _root->_left;
         _root->_left = _root->_right;
         _root->_right = ptmp;
         if (_root->_left)
             Mirrorcursively(_root->_left);
         if (_root->_right)
             Mirrorcursively(_root->_right);
       }

方法二:非遞歸法

用非遞歸方法實作，借助棧來完成

void Iteratively(Node *_root)
     {
         if (_root == NULL)
             return;
         stack<Node*> s;
         s.push(_root);
         while (!s.empty())
         {
             Node *top = s.top();
             s.pop();
             Node *ptmp = top->_left;
             top->_left = top->_right;
             top->_right = ptmp;
             if (top->_left)
                 s.push(top->_left);
             if (top->_right)
                 s.push(top->_right)
         }
    }

求二叉樹中最遠的兩個節點之間的距離

題目：如果我們把二叉樹看做圖，父子節點之間的連線看成是雙向的，我們姑且定義“距離”為兩個節點之間邊的個數。寫一個程式求一棵二叉樹中相距最遠的兩個節點之間的距離。

思路：

1、如果最遠距離的兩個節點都經過了根節點，則最遠距離就是左邊最深的深度到根節點的距離+右邊最深的深度到根節點的距離

如下圖所示，樹中相距最遠的兩個節點為A,B，最大距離為6。

2、如果具有最遠距離的兩個節點不經過根節點，那麼最遠距離就是根節點上某個子樹上面的兩個節點

如下圖所示，樹中相距最遠的兩個節點為A,B，最大距離為5。

代碼實作如下：

int GetFarDistance()
       {
              int distance = -1;
              _Height(_root,distance);
              return distance;
       }
protected:
       int _Height(Node* root, int& distance)
       {
              if (root == NULL)
              {
                     return 0;
              }
              int leftH = _Height(root->_left);
              int rightH = _Height(root->_right);
              if (leftH+rightH > distance)
              {
                     distance = leftH + rightH;
              }
              return leftH > rightH ? leftH+1 : rightH+1;
       }

由前序周遊和中序周遊重建二叉樹

題目：輸入某二叉樹的前序周遊和中序周遊的結果，請重建出該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建二叉樹并傳回。

思路：

1、在二叉樹的前序周遊序列中，第一個數字總是樹的根結點的值。但在中序周遊序列中，根結點的值在序列的中間，左子樹的結點的值位于根結點的值的左邊，而右子樹的結點的值位于根結點的值的右邊。是以我們需要掃描中序周遊序列，才能找到根結點的值。

2、如下圖所示，前序周遊序列的第一個數字1就是根結點的值。掃描中序周遊序列，就能确定根結點的值的位置。根據中序周遊特點，在根結點的值1前面的3個數字都是左子樹結點的值，位于1後面的數字都是右子樹結點的值。

3、同樣，在前序周遊的序列中，根結點後面的3個數字就是3個左子樹結點的值，再後面的所有數字都是右子樹結點的值。這樣我們就在前序周遊和中序周遊兩個序列中，分别找到了左右子樹對應的子序列。

4、既然我們已經分别找到了左、右子樹的前序周遊序列和中序周遊序列，我們可以用同樣的方法分别去建構左右子樹。也就是說，接下來的事情可以用遞歸的方法去完成。

代碼實作如下：

#include <iostream>
#include <vector>
using namespace std;
// Definition for binary tree
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/* 先序周遊第一個位置肯定是根節點node，
中序周遊的根節點位置在中間p，在p左邊的肯定是node的左子樹的中序數組，p右邊的肯定是node的右子樹的中序數組
另一方面，先序周遊的第二個位置到p，也是node左子樹的先序子數組，剩下p右邊的就是node的右子樹的先序子數組
把四個數組找出來，分左右遞歸調用即可
 */
class Solution {
public:
struct TreeNode* reConstructBinaryTree(vector<int>       pre,vector<int> in) {

int in_size = in.size();//獲得序列的長度
2 if (in_size == 0)
return NULL;
//分别存儲先序序列的左子樹，先序序列的右子樹，中序序列的左子樹，中序序列的右子樹
vector<int> pre_left, pre_right, in_left, in_right;
int val = pre[0];//先序周遊第一個位置肯定是根節點node,取其值
//建立一個樹結點，并傳入結點值
TreeNode* node = new TreeNode(val);//root node is the first element in pre
//p用于存儲中序序列中根結點的位置
int p = 0;
for (p; p < in_size; ++p){
if (in[p] == val) //Find the root position in in 
break;        //找到即跳出for循環
}
for (int i = 0; i < in_size; ++i){
if (i < p){
 //建立中序序列的左子樹和前序序列的左子樹
in_left.push_back(in[i]);//Construct the left pre and in 
pre_left.push_back(pre[i + 1]);//前序第一個為根節點,+1從下一個開始記錄
 }
else if (i > p){
 //建立中序序列的右子樹和前序序列的左子樹
in_right.push_back(in[i]);//Construct the right pre and in 
 pre_right.push_back(pre[i]);
}
 }
//取出前序和中序周遊根節點左邊和右邊的子樹
//遞歸，再對其進行上述所有步驟，即再區分子樹的左、右子子數，直到葉節點
node->left = reConstructBinaryTree(pre_left, in_left);
node->right = reConstructBinaryTree(pre_right, in_right);
return node;
  }
 };

作者：wyn126

來源：CSDN

原文：https://blog.csdn.net/wyn126/article/details/81450285

二叉樹面試題

繼續閱讀

2021-08-13c++——類之操作符重載

[轉]ISUP信令的IAM消息詳細内容

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器