剑指 Offer 55 - I. 二叉树的深度

难度简单104
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。

非递归写法

  1. class Solution {
  2. public:
  3.     int maxDepth(TreeNode* root) {
  4.         if(root == nullptr){
  5.             return 0;
  6.         }
  7.         queue<TreeNode*> qs;
  8.         int ans = 0;
  9.         qs.push(root);
  10.         while(!qs.empty()){
  11.             int size = qs.size();
  12.             while(size --){
  13.                 TreeNode* node = qs.front();
  14.                 qs.pop();
  15.                 if(node->left) qs.push(node->left);
  16.                 if(node->right) qs.push(node->right);
  17.             }
  18.             ans ++;
  19.         }
  20.         return ans;
  21.     }
  22. };

543. 二叉树的直径

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

示例 :
给定二叉树
1
/ \
2 3
/ \
4 5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

  1. class Solution {
  2. private:
  3.     int ans;
  4. public:
  5.     int calDepth(TreeNode* root){
  6.         if(root == nullptr){
  7.             return 0;
  8.         }
  10.         int left = calDepth(root->left);
  11.         int right = calDepth(root->right);
  12.         //求的是最大的路径长度
  13.         ans = max(ans, left + right + 1);
  14.         //max(l,r)+1是当前节点的深度
  15.         return max(left, right) + 1;
  17.     }
  18.     int diameterOfBinaryTree(TreeNode* root) {
  19.         ans = 0;
  20.         calDepth(root);
  21.         return ans - 1;
  22.     }
  23. };