543&1367.二叉树的直径、最大深度

• 543.二叉树的直径
  • 解题思路
• 1367.二叉树的最大深度
  • 解题思路

543.二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例：

解题思路

https://leetcode-cn.com/problems/diameter-of-binary-tree/solution/shi-pin-jie-shi-di-gui-dai-ma-de-yun-xing-guo-chen/

class Solution {
public:
    int ans=1;
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return ans-1;
    }
    int depth(TreeNode* root){
        if(!root)return 0;
        int L=depth(root->left);
        int R=depth(root->right);
        ans=max(ans,L+R+1);
        return max(L,R)+1;
    }
};

1367.二叉树的最大深度

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

示例：

解题思路

• 递归

//递归法
class Solution {
public:
    int ans=0;
    int maxDepth(TreeNode* root) {
        if(!root)return 0;
        return depth(root);
    }
    int depth(TreeNode* root){
        if(!root)return 0;
        int L=depth(root->left);
        int R=depth(root->right);
        ans=max(L,R)+1;
        return ans; 
    }
};

• 非递归

class Solution {
public:
    int maxDepth(TreeNode* root) {
        //层次遍历
        if(!root)return 0;
        int maxdepth=0;int qSize=0;
        queue q;
        q.push(root);
        while(!q.empty()){
            maxdepth++;  
            qSize=q.size();
            while(qSize--!=0){//tips!
                root=q.front();
                q.pop();
                if(root->left)q.push(root->left);
                if(root->right)q.push(root->right);

            } 
        }
        return maxdepth;
    }
};