最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

【环球报资讯】二叉树的深度之DFS、BFS

来源：博客园


【资料图】

问题：二叉树的深度面试题55 - I. 二叉树的深度（后序遍历、层序遍历，清晰图解） - 二叉树的深度 - 力扣（LeetCode）

计算树的深度需要遍历树的所有节点，采用 深度优先搜索DFS、广度优先搜索BFS；

常见的DFS：先序、中序、后序；

常见的BFS：层序遍历

方法一：DFS之后续遍历，递归方式；max(左子树的深度，右子树的深度)

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    int maxDepth(TreeNode* root) {        if(root == nullptr) return 0;        return max(maxDepth(root->left), maxDepth(root->right))+1;    }};

方法二：BFS之层序遍历，用队列实现，

队列中放每层的节点，首先放入第一层的头节点，其后循环遍历这一层的所有节点：将其复制出来然后pop掉，然后遍历队列中该节点的左右子节点，将其放入队列尾中；

同时设置一个计数器，每遍历一层计数器加一；

遍历完一层之后遍历下一层，直到队列为空；

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    int maxDepth(TreeNode* root) {        if(root == nullptr) return 0;        queueq;        q.push(root);        int res =0;        while(!q.empty()){            for(int i = q.size();i>0;--i){                TreeNode* qnode = q.front();                q.pop();                if(qnode->left != nullptr) q.push(qnode->left);                if(qnode->right != nullptr) q.push(qnode->right);            }            ++res;        }        return res;    }};

关键词： 广度优先搜索 深度优先搜索