代码随想录刷题随记14-二叉树3

104.二叉树的最大深度

leetcode 链接

递归

class Solution {
public:int sub(TreeNode * root){if(root->left==nullptr&&root->right==nullptr)return 1;int lefth=root->left==nullptr?0:sub(root->left);   int righth=root->right==nullptr?0:sub(root->right); return lefth>=righth ? lefth+1:righth+1;}int maxDepth(TreeNode* root) {if(root==nullptr)return 0;return sub(root);}
};

本题也可以利用上一节层次遍历求解。

111.二叉树的最小深度

leetcode 链接
不能这么写：

int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);
return result;

必须要满足是到叶子结点的高度
注意误区：

非递归版本：仍然可以利用层次遍历求解

class Solution {
public:int minDepth(TreeNode* root) {if(root==nullptr)return 0;queue<TreeNode *> myqueue;myqueue.push(root);int height=1;int retheight=INT_MAX;while(!myqueue.empty()){int size=myqueue.size();for(int i=0;i<size;i++){       TreeNode * cur=myqueue.front();myqueue.pop();if(cur->left!=nullptr)myqueue.push(cur->left);if(cur->right!=nullptr){myqueue.push(cur->right);}if(cur->left==nullptr&&cur->right==nullptr)return height;}height++;}      return height;     }
};

222.完全二叉树的节点个数

leetcode 链接
可以按照普通的二叉树层次遍历所有的节点统计个数
也可以利用完全二叉树的性质

class Solution {
public:int countNodes(TreeNode* root) {if(root==nullptr)return 0;TreeNode * left=root->left;TreeNode * right=root->right;int lefth=0;int righth=0;while(left!=nullptr){left=left->left;lefth++;}while(right!=nullptr){right=right->right;righth++;}if(lefth==righth)return (2<<lefth)-1;return countNodes(root->left)+countNodes(root->right)+1;}
};