二叉树题目汇总

程序员文章站 2022-06-17 19:50:18

...

内容会持续更新，有错误的地方欢迎指正，谢谢!

前言

宏观概念：有向图可退化为树可退化为链表
二叉树虽然简单，但是与链表相比，树的题目涉及到大量指针，细微之处更能特别考验程序员的能力，所以，若想加大面试难度，树的题目是不二之选，博主在此列出一些二叉树常见的题型。

思路：只有画出二叉树的图+具体的例子（一边看着图形一边讲解，面试官会更轻松地理解你的思路，并觉得你好沟通），才好找出题目的规律，才好发现错误和漏洞，才好设计出可行的算法。也就是，先想（讲）清楚思路，得到肯定后，再码代码！
注意：先考虑边界测试：每一次需要访问地址的时候都要问自己这个地址有没有可能是nullptr，如果是nullptr那怎么处理；再考虑功能测试：完全二叉树和非完全二叉树。
用递归实现的话，边界测试一般需要以下判断：

    if(pRoot==nullptr)
        return;//或return 0; 或return nullptr;

小套路：如果递归函数为bool型，则双重递归函数要么在if中，要么就在return中。例子：

if(Func(pRoot->left)&&Func(pRoot->right))
    return true;
return false;
//等价于：
return Func(pRoot->left)&&Func(pRoot->right);
//但是，第一种可以加一些处理操作：
if(Func(pRoot->left)&&Func(pRoot->right))
{
    //可以加一些cout用于输出，或者加一些if用于判断是否返回true等等
    return true;
}
return false;

（不用考虑val是否相同。结构相同：两颗二叉树的两个根结点对应的的左子树和右子树结构相同。）
遍历。return 判断两棵树的左子树是否相同&&判断两棵树的右子树是否相同；
什么叫相同？两个对应的结点同时为空
什么叫不同？两个对应的结点中只有一个结点为空
那都不为空时呢？去递归呗。

8、求二叉树的镜像（又叫翻转二叉树）

遍历。对于根结点，交换其左右子树，左右子树各自去递归。

补充的问题：判断是不是对称的二叉树。方法：bool函数，前序遍历，对应的结构和对应的值都要相等，return里左右子树继续去递归。

小窍门：该类问题很抽象，图形能使抽象的问题具体化、形象化，得到规律。比如：二叉树、链表、二维数组等问题都可以采用画图的方法来分析。空想很难能想明白题目中隐含的规律。

9、求两个结点的最低公共祖先结点

题目1：若这是一棵二叉查找树，那么就简单了：1.当根结点的值大于两个这结点的值，则继续在左子树中找；2.当根结点的值小于两个这结点的值，则继续在右子树中找；3.当根结点的值在这两个结点的值之间，则该根结点就是最低公共祖先结点。
题目2：若这不是一棵二叉树，只是普通的树，每个结点除了根结点外都有指向父结点的指针：这不就是求两个链表的第一个公共结点嘛。
题目3：就是下方的第9题，若这是一颗二叉树（题目偏难），则遍历后，需有如下判断:

//对一个根结点来说，分别在左右子树中找到了目标结点，则该根结点就是所求结点。
if (left!=nullptr && right!=nullptr)
    return pRoot;
//对一个根结点来说，只在左子树或右子树找到了目标结点，则返回找到的结点。
return left!=nullptr ? left : right;

10、求任意两结点距离

遍历。先找到两个结点的最低公共祖先结点，然后分别计算最低公共祖先结点（根结点）与它们的距离，最后相加即可。也就是两个函数，第二个函数用于求距离：遍历，先在左子树中找，if没找到的话，再在右子树中找，找到了则return res+1；最后都没找到就return -1。

11、找出二叉树中某个结点的所有祖先结点

遍历。bool递归函数。if(找出该结点的左子树中某个结点的所有祖先结点||找出该结点的右子树。。。)，如果为if条件为true，则输出该结点。

12、判断二叉树是否是平衡二叉树（了解）

遍历。if(判断左子树是否是平衡二叉树&&判断右子树是否是平衡二叉树)，再在这个if中，if(判断深度差left-right的绝对值是否小于1)。。。挺有挑战的一道题。

13、二叉树中和为某一值的路径

前序遍历，和expectNumber作为递归函数的一个参数，每降低一层，expectNumber就要减去刚才那个结点的值。
定义一个二维vector容器res和一个一维vector容器temp。每路过一个结点，就将该结点装进temp。若走到了叶节点，且该条路的和刚好等于expectNumber，则将这条路（temp记录的）装入res；若此时和不等于expectNumber，就回溯。
如何回溯？
在双重递归后加上temp.pop_back() 弹出最后那个元素，再装入下一个要遍历的元素，不就好了。

14、根据前序和中序重建二叉树

构建左子树的前序中序和右子树的前序中序，再分左右子树递归。
小窍门：当我们发现大问题和小问题在本质上是一致时，便可用递归解决，所以二叉树的题基本都用递归。由于要遍历二叉树，所以基本都用双重递归。

15、二叉搜索树与双向链表

中序遍历。简单题。定义两个变量，一个变量用于记录头结点，一个变量用于改变指向。
小窍门：一定要先画图分析，通过分析得到思路后，再动手写代码，不要一开始就写，不然越写越懵。

1、前序遍历，中序遍历，后序遍历

要么用递归（递归其实就是栈的思想），要么就用栈+迭代。
其实，其他题目都是在间接地考察这三种遍历，尤其是前序遍历考得多。所以，该题是核心。

前序遍历-根左右

//前序遍历递归实现
void PreOrder(TreeNode* pRoot)
{
    if (pRoot== nullptr)
        return;
    cout << pRoot->val << " "; // 先输出当前结点
    PreOrder(pRoot->left);     // 然后输出左孩子
    PreOrder(pRoot->right);    // 最后输出右孩子
}

//前序遍历迭代实现（了解）
void PreOrder(TreeNode* pRoot)
{
    if (pRoot== nullptr)
        return;
    stack<TreeNode*> S;// 用栈来模拟递归
    cout << pRoot->val<< " ";
    S.push(pRoot);
    pRoot= pRoot->left;

    while (!S.empty())
    {
        while (pRoot)
        {
            cout << pRoot->val << " "; // 先输出当前结点  
            S.push(pRoot);
            pRoot= pRoot->left;         // 然后输出左孩子
        }                              // while 结束意味着左孩子已经全部输出
        pRoot= S.top()->right;         // 最后输出右孩子
        S.pop();
    }
}

中序遍历-左根右

//中序遍历递归实现，由于迭代实现代码量大而思路和递归一样，所以这里省略之。
void InOrder(ListNode* pRoot)
{
    if (pRoot== nullptr)
        return;
    InOrder(pRoot->left);     // 先输出左孩子
    cout << pRoot->val<< " ";  // 然后输出当前结点
    InOrder(pRoot->right);    // 最后输出右孩子
}

后序遍历-左右根

//后序遍历递归实现
void PostOrder(ListNode* pRoot)
{
    if (pRoot== nullptr)
        return;
    PostOrder(pRoot->left);   // 先输出左孩子
    PostOrder(pRoot->right);  // 然后输出右孩子
    cout << pRoot->val<< " ";  // 最后输出当前结点
}

2、层次遍历

也就是每层从左到右的输出，这层搞完了再搞下一层。

//使用先进先出的队列queue或两端都可以进出的deque
void LevelOrder(TreeNode* pRoot)
{
    if(pRoot==nullptr)
        return;
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(pRoot);
    TreeNode* p=pRoot;
    while(!nodeQueue.empty())
    {
        p=nodeQueue.front();
        cout<<p->val<<" ";
        nodeQueue.pop();
        if(p->left)
            nodeQueue.push(p->left);
        if(p->right)
            nodeQueue.push(p->right);
    }
}

（类似题）把二叉树打印成多行

从上到下按层打印二叉树，同一层结点从左至右输出，每一层输出一行。
解法：添加两个变量，变量toBePrinted表示当前层还未打印的结点数，变量nextLevel表示下一层的结点数。每把一个子结点加入队列，nextLevel加1；每打印一个子结点并将其移除队列，toBePrinted减1。当toBePrinted为0，则换行。

（类似题）把二叉树按之字形打印

解法：类似于上题，这里添加两个栈，一个栈是当前层的输出栈，一个是下一层的存储栈。

3、求树的结点数

int CountNode(TreeNode* pRoot)
{
    if(pRoot==nullptr)
        return 0;
    return 1+CountNode(pRoot->left)+CountNode(pRoot->right);
}

4、求树的叶子数

没错，就是只求叶子的个数。

int CountLeaf(TreeNode* pRoot)
{
    if(pRoot==nullptr)
        return 0;
    if(pRoot->left==nullptr&&pRoot->right==nullptr)
        return 1;
    return CountLeaf(pRoot->left)+CountLeaf(pRoot->right);
}

5、求二叉树第 k 层的结点个数

和上一题很像。
每降低一层，k就要-1，比如求相对根结点第三层k=3的结点数，k-1=2后，就变成了求相对次根结点的第二层的结点数。k再-1=1后，就变成了求相对次次根结点的第一层（即当前层）的结点数。

int KNodeCount(TreeNode* pRoot,int k)
{
    if(pRoot==nullptr)
        return 0;
    if(k<=0)
        return 0;
    if(k==1)
        return 1;
    return KNodeCount(pRoot->left,k-1)+KNodeCount(pRoot->right,k-1);
}

6、求树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点形成的最长路径的长度为树的深度。

//前序的思想
int TreeDepth(TreeNode* pRoot)
{
    if(pRoot==nullptr)
        return 0;
    int leftVal=TreeDepth(pRoot->left);
    int rightVal=TreeDepth(pRoot->right);
    return (leftVal>rightVal)?(leftVal+1):(rightVal+1);
}

7、判断两棵二叉树是否结构相同

不用考虑val是否相同。结构相同：两颗二叉树的两个根结点对应的的左子树和右子树结构相同。

//依次判断左左和右右是否相同，一旦不相同就会返回false
bool IsStructEqual(TreeNode* pRoot1,TreeNode* pRoot2)
{
    if(pRoot1==nullptr&&pRoot2==nullptr)
        return true;
    if(pRoot1==nullptr||pRoot2==nullptr)
        return false;
    return IsStructEqual(pRoot1->left,pRoot2->left)&&
    IsStructEqual(pRoot1->right,pRoot2->right);
}

8、求二叉树的镜像

//对于每个结点，我们交换它的左右孩子即可。
void Mirror(TreeNode *pRoot) 
{
    if(pRoot==nullptr)
        return;
    TreeNode *temp=pRoot->left;
    pRoot->left=pRoot->right;
    pRoot->right=temp;
    Mirror(pRoot->left);
    Mirror(pRoot->right);
}
//把两个递归函数放到交换之前，也行，如此，只不过是先交换叶节点而已罢了。

（类似题）对称的二叉树

判断一颗二叉树是不是对称的。如果一个二叉树同此二叉树的镜像是一样的，则为对称的。

    bool isSymmetrical(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;
        //val相等，此时不能直接return true;还要继续往下层结点判断，不然就忽略了下一层的情况。

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

9、求两个结点的最低公共祖先结点

这道题需要好好画图体会：对于根结点来说，有两种情况：两个目标点在两边或同一边。

//先递归到最下层最左边的左右结点，再依次往上处理根结点。
ListNode* LowestAnc(ListNode* pRoot, ListNode* target1, ListNode* target2)
{
    if (pRoot== nullptr)
        return nullptr;
    if (pRoot== target1 || pRoot== target2)//找到目标结点则返回目标结点，表明已找到了。
        return pRoot;
    ListNode* left = LowestAnc(pRoot->left, target1, target2);
    ListNode* right = LowestAnc(pRoot->right, target1, target2);
    //对一个根结点来说，分别在左右子树中找到了目标结点，则该根结点就是所求结点。
    if (left!=nullptr && right!=nullptr)
        return pRoot;
    //对一个根结点来说，只在左子树或右子树找到了目标结点，则返回找到的结点。
    return left!=nullptr ? left : right;
}

10、求任意两结点距离

二叉树题目汇总

思路：先找到两个结点的最低公共祖先结点，然后分别计算最低公共祖先结点与它们的距离，最后相加即可。

int DistanceNodes(ListNode* pRoot, ListNode* target1, ListNode* target2)
{
    ListNode* anc = FindLCA(pRoot, target1, target2);  //找到最低公共祖先结点
    int level1 = CalDistance(anc , target1); //CalDistance()求两个指定结点的距离
    int level2 = CalDistance(anc , target2);
    return level1 + level2;
}

//求两个指定结点的距离
int CalDistance(TreeNode* pRoot,TreeNode* target)
{
    if(pRoot==nullptr)
        return -1;
    if(pRoot==target)
        return 0;
    int res=CalDistance(pRoot->left,target);//在左子树中找
    if(res==-1)//左子树中没找到
        res=CalDistance(pRoot->right,target);//再到右子树中找
    if(res！=-1)//找到了，则+1
        return res+1;
    return -1;//左右子树里都没找到
}

上面两道题是典型的面试题，第一题会做的话，那么加大难度，做第二题，第二题如果搞定，那稳了。

11、找出二叉树中某个结点的所有祖先结点

//再来一道类似的题，这道题简单多了
bool FindAllAnc(TreeNode* pRoot,TreeNode* target)
{
    if(pRoot==nullptr)
        return false;
    if(target==pRoot)
        return true;
    if(FindAllAnc(pRoot->left,target)||FindAllAnc(pRoot->right,target))
    {
        cout<<pRoot->val<<" ";
        return true;//找到了，层层返回true
    }
    return false;
}
//该递归函数定义为bool，所以函数的返回值可作if的条件。若函数为其他类型，就需定义一个变量用于存储。

12、判断二叉树是否是平衡二叉树（了解）

平衡二叉树：左右两个子树的高度差不超过1。

    bool IsBalanced_Solution(TreeNode* pRoot) 
    {
        int depth=0;
        return IsBalanced_Solution(pRoot,depth);
    }
    bool IsBalanced_Solution(TreeNode* pRoot,int& depth)//depth变量传引用或者传地址都行
    {
        if(pRoot==nullptr)//说明已经到达了叶节点的空结点
        {
            depth=0;
            return true;
        }

        int left=0,right=0;
        //会把根节点的每一条路都走到叶节点，到叶节点后，才开始执行if的内容（往上走到根节点）
        if(IsBalanced_Solution(pRoot->left,left)&&IsBalanced_Solution(pRoot->right,right))
        {
            if((left-right<=1)&&(left-right>=-1))
            {
                depth=1+((left>right)?left:right);
                return true;
            }
        }
        return false;//一旦有一处为false，则最上层那次递归函数一定返回false
    }

13、二叉树中和为某一值的路径

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。用vector<vector<int>>保存每条路径。

    vector<vector<int> > res;
    vector<int> temp;//定义为全局变量，就不需要把它当作递归函数的参数了
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) 
    {
        if(root==nullptr)
            return res;
        GetPath(root,expectNumber);
        return res;
    }
    void GetPath(TreeNode* root,int expectNumber)
    {
        //前序思想
        if(root==nullptr)
            return;
        temp.push_back(root->val);//每路过一个结点，就将该结点装进来

        //若走到了叶节点，且该条路的和刚好等于expectNumber，则将temp装入res
        if(root->left==nullptr&&root->right==nullptr&&root->val==expectNumber)
            res.push_back(temp);
        GetPath(root->left,expectNumber-root->val);
        GetPath(root->right,expectNumber-root->val);
        temp.pop_back();//每次递归的最后，都要弹出temp中上次那个结点，以便装入下个结点
    }

14、根据前序和中序重建二叉树

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

    //不就是构建 左子树的前序中序 和 右子树的前序中序，再分左右子树递归吗？
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) 
    {
        if(pre.size()==0||vin.size()==0)
            return nullptr;
        TreeNode *pRoot=new TreeNode(pre[0]);
        vector<int> leftPre,leftVin,rightPre,rightVin;
        int vinRootNum;
        for(int i=0;i<vin.size();++i)
        {
            if(vin[i]==pRoot->val)
                vinRootNum=i;
        }
        for(int i=0;i<vinRootNum;++i)
        {
            leftVin.push_back(vin[i]);
            leftPre.push_back(pre[i+1]);
        }
        for(int i=vinRootNum+1;i<vin.size();++i)
        {
            rightVin.push_back(vin[i]);
            rightPre.push_back(pre[i]);
        }

        //别忘了连接各个返回的结点成一棵树
        pRoot->left=reConstructBinaryTree(leftPre,leftVin);//去构建左子树
        pRoot->right=reConstructBinaryTree(rightPre,rightVin);//去构建右子树
        return pRoot;
    }

//i为中序里根结点的索引，构建左子树的前序中序 和 右子树的前序中序 的另一种方法：
vector<int> leftPre(pre.begin()+1,pre.begin()+i+1);
vector<int> leftVin(vin.begin(),vin.begin()+i);
vector<int> rightPre(pre.begin()+i+1,pre.end());
vector<int> rightVin(vin.begin()+i+1,vin.end());

（类似题）二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历序列，返回true或false。
解法：序列的最后一个元素是根结点，根据该根结点就可以判断出左子树和右子树的序列，因为左子树的元素都小于根结点，右子树的元素都大于根结点。那么双重递归下去不就解决问题了。一个原则：左子树的所有元素恒小于根结点，右子树的所有元素恒大于根结点。比如{4,2,3}就不行，因为根结点3的右子树序列{4,2}中2小于3；再比如{2,4,1,3}中3的右子树序列{4,1}中的1小于3，所以不行。

15、二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

    TreeNode *pHead=nullptr,*pNode=nullptr;//每次递归都不能被重置，所以要定义为全局变量
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==nullptr)
            return nullptr;
        Convert(pRootOfTree->left);
        if(pHead==nullptr&&pNode==nullptr)
            pHead=pNode=pRootOfTree;
        else
        {
            pNode->right=pRootOfTree;
            pRootOfTree->left=pNode;
            pNode=pRootOfTree;
        }
        Convert(pRootOfTree->right);
        return pHead;
    }

相关标签：二叉树数据结构面试

上一篇：不同的二叉搜索树 II

下一篇：分发饼干

二叉树题目汇总

前言

目录

1、前序遍历，中序遍历，后序遍历

2、层次遍历

3、求树的结点数

4、求树的叶子数

5、求二叉树第k层的结点个数

6、求树的深度

7、判断两颗二叉树是否结构相同

8、求二叉树的镜像（又叫翻转二叉树）

9、求两个结点的最低公共祖先结点

10、求任意两结点距离

11、找出二叉树中某个结点的所有祖先结点

12、判断二叉树是否是平衡二叉树（了解）

13、二叉树中和为某一值的路径

14、根据前序和中序重建二叉树

15、二叉搜索树与双向链表

1、前序遍历，中序遍历，后序遍历

前序遍历-根左右

中序遍历-左根右

后序遍历-左右根

2、层次遍历

（类似题）把二叉树打印成多行

（类似题）把二叉树按之字形打印

3、求树的结点数

4、求树的叶子数

5、求二叉树第 k 层的结点个数

6、求树的深度

7、判断两棵二叉树是否结构相同

8、求二叉树的镜像

（类似题）对称的二叉树

9、求两个结点的最低公共祖先结点

10、求任意两结点距离

11、找出二叉树中某个结点的所有祖先结点

12、判断二叉树是否是平衡二叉树（了解）

13、二叉树中和为某一值的路径

14、根据前序和中序重建二叉树

（类似题）二叉搜索树的后序遍历序列

15、二叉搜索树与双向链表

中原工学院改名最新消息？2021年河南筹备更名的大学名单汇总

2021年中国985大学排名一览表（最全榜单汇总）

python3编码问题汇总

Java中二叉树的建立和各种遍历实例代码

iOS弹幕开发中遇到的问题汇总

iOS常用组件之高效切圆角的方法汇总

苹果表Apple Watch 4月10日凌晨00:01开始接受预定 各地具体时间汇总

SQLServer中汇总功能的使用GROUPING,ROLLUP和CUBE

2021年山西独立院校转设最新消息：山西转设为公办的独立学院名单汇总

2021年贵州独立大学转为公办大学有哪些？附贵州独立学院转设情况汇总

苹果表Apple Watch 4月10日凌晨00:01开始接受预定各地具体时间汇总