剑指offer 二叉树的深度

Dear 丶 2024-04-17 05:59 70阅读 0赞

# [剑指offer题型分类及各题的代码及解题思路][offer] #

## 1、题目描述 ##

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。（设只有根节点时，深度为1）

## 2、初始结构定义 ##

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {}
    };*/
    class Solution {
    public:
        int TreeDepth(TreeNode* pRoot){}
    };

## 3、解题思路及代码 ##

**方法一：递归法**

**思路：**

*  如果一棵树只有一个结点，那么它的深度为1；
 *  如果一棵树根节点只有左右子树其中一个，那么树的深度为左子树深度加1或右子树深度加1；
 *  如果一棵树既有左子树又有右子树，那么深度即为左右子树深度的较大值加1；

class Solution {
    public:
        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);
        }
    };

方法二：非递归法

经典的非递归**层次遍历**：利用辅助队列，先将头节点入队列，当队列不空时出队列的节点记为curr，当curr左节点不空时入队列，其右节点不空时入队列，如此循环即可。

求深度：构造变量n记录当前层访问到的节点数，width记录当前层的总个数，每当访问过一层层数depth++；

此种方法同时可以求最大宽度，访问第几层的第几个节点，是一种通用方法！

class Solution 
    {
    public:
        int TreeDepth(TreeNode* pRoot)
        {
            if(pRoot == NULL)
                return 0;
            
            queue<TreeNode*> q;    //构造辅助队列
            TreeNode* curr;    //记录当前节点
            int depth = 0;    //初始深度为0；
            int n,width;    //n记录访问到当前层的第几个,widtd为当前层的宽度
            q.push(pRoot);    //头结点入队列
            //队列不空 循环记录深度
            while(!q.empty())
            {
                //新的一层n赋为0
                n = 0;
                //当前队列里的节点即为该层的所有节点
                width = q.size();
                //循环访问该层的所有节点 
                while(n < width)
                {
                    //访问队列的头
                    curr = q.front();
                    q.pop();    //访问完的结点出队
                    if(curr->left != NULL)
                    {
                        q.push(curr->left);
                    }
                    if(curr->right != NULL)
                    {
                        q.push(curr->right);
                    }
                    n++;
                }
                depth++;    //访问完一层，深度加1
            }
            return depth;
        }
    };

[offer]: https://blog.csdn.net/qq_26079093/article/details/96605538