| 【每日挠头算法题(9)】二叉树的直径 | 您所在的位置：网站首页 › 某二叉树后序遍历是dabec › 【每日挠头算法题(9)】二叉树的直径 |
【每日挠头算法题(9)】二叉树的直径
|
文章目录
一、二叉树的直径思路：二叉树的深度优先搜索具体代码如下：
二、二叉树的层序遍历思路：借助队列实现具体代码如下：
总结：
一、二叉树的直径
点我直达~
根据题目要求，求二叉树的直径，就是求二叉树的任意一个节点左右子树的最大深度，左右子树的最大深度的和就是所求的路径。 看下图理解：
对于节点2来说，其左子树的最大深度为2，说明一定有一条大小为2的路径直通左子树的叶子节点，其右子树的最大深度为2，说明一定有一条大小为2的路径直通右子树的叶子节点，这样从以节点2为根节点的树的任意一个叶子节点一定有一条大小为4的路径到达另一个叶子节点。 所以我们需要做的就是找到任意一个节点的左右子树的最大深度。 按照深度优先搜索的算法，我们首先持续遍历左子节点。如果节点为空，返回0 将左右子树都遍历后，比较左右子树的高度，再返回大的高度+1就是当前节点的高度。 注意：在这个过程，我们需要用一个全局变量max来更新每一次遍历某一个节点之后他的最长路径，也就是该节点的左右子树的高度之和。 具体代码如下： class Solution { public: int MAX; //记录每一次遍历一个节点的左右子树后的最长路径 int depth(TreeNode* root) { if(root == nullptr) return 0; int l = depth(root->left);//递归左子树的最大深度 int r = depth(root->right);//递归右子树的最大深度 if(l+r > MAX) MAX = l+r; // 求出左右子树最大深度+1，就是到自己的深度 return max(l,r) +1 ; } int diameterOfBinaryTree(TreeNode* root) { MAX = 0; depth(root); return MAX ; } };时间复杂度O(n),空间复杂度O(n)：最坏情况下为链式结构；最好情况下为平衡二叉树：O(logN); 二、二叉树的层序遍历点我直达~
二叉树的层序遍历，实际上就是广度优先搜索，从根往下从左到右逐一遍历每一层的节点。 所以我们需要借助一个队列q1，如果该根节点不为空，将该节点入队 然后计算队列中的元素数量，即为这一层的节点个数 先取出该队列的队头元素，然后将该节点的val值存入到顺序表v1中，如果该节点的左右子节点均不为空，则带动该节点的左右子节点入队，然后再将该节点出队，最后重新计算该队列的元素大小。 注意：每遍历完一层，就需要将v1加入到专门存储顺序表的顺序表v之中。 不断重复上述过程，直到该树遍历完为止。 具体代码如下： class Solution { public: vector levelOrder(TreeNode* root) { vector v; queue q1; //入队 if(!root) return v; q1.push(root); while(!q1.empty()) { //存进顺序表前先计算当前队列有多少个元素。 int size = q1.size(); vector v1; //存入顺序表 while(size--) { TreeNode* root = q1.front(); v1.push_back(root->val); if(root->left) q1.push(root->left); if(root->right) q1.push(root->right); q1.pop(); } //然后将v1存入v中并刷新 v.push_back(v1); } return v; } };时间复杂度O(n)，遍历完每一个节点；空间复杂度O(n)，当二叉树退化到链式结构时，深度为n,系统维护的辅助栈就为n的大小；最好情况为平衡二叉树时，高度logN，空间复杂度O(logN) 总结：通过写这道二叉树的直径，越发觉得递归是一个比较神奇且难以理解的东西，还有这个最长路径，我是看了不下5次的答案才看懂最长路径为什么等于一个节点的左右子树的深度和。 二叉树的层序遍历，需要借助队列实现，这个还是比较简单的，相对于官方标记层序遍历是中等题，个人更认为二叉树的直径这道题是中等题。 |
【本文地址】