104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
关键词： 递归、回溯
递归三件套：
- 参数设置与返回值设置
- 需要遍历整颗树，期间会改变deepth的值，所以不需要返回值
- 参数只需要TreeNode*和一个代表访问节点层的树的高度，用来与全局deepth作比较来确定二叉树最深的深度
- 终止条件
- 终止条件即该节点为叶子节点的时候就可以返回了
- 本层逻辑
- 判断是否有左右孩子，如果有则深入访问，注意回溯cur_deepth
完整代码：
class Solution { public: int deepth = 0; void backTracking(TreeNode *cur, int cur_deepth){ deepth = deepth < cur_deepth ? cur_deepth : deepth; // 如果本层深度比历史记录深度大则替换 if(!cur->left && !cur->right) return; if(cur->left){ cur_deepth++; backTracking(cur->left,cur_deepth); cur_deepth--; // 回溯 } if(cur->right){ cur_deepth++; backTracking(cur->right,cur_deepth); cur_deepth--; //回溯 } } int maxDepth(TreeNode* root) { if(root == nullptr) return deepth; deepth++; backTracking(root, deepth); return deepth; } };
改动
上面的代码只稍作改动就可以作为二叉树的最小深度的题解
- 将deepth的初始值设置为最大数INT_MAX
- 改变三元运算符中的条件
- 且只在访问到叶子节点时才进行比较
完整代码
class Solution { public: int deepth; void backTracking(TreeNode *cur, int cur_deepth){ if(!cur->left && !cur->right) { deepth = deepth > cur_deepth ? cur_deepth : deepth; // 如果本层深度比历史记录深度大则替换 return ; } if(cur->left){ cur_deepth++; backTracking(cur->left,cur_deepth); cur_deepth--; // 回溯 } if(cur->right){ cur_deepth++; backTracking(cur->right,cur_deepth); cur_deepth--; //回溯 } } int minDepth(TreeNode* root) { deepth = 0; if(!root) return deepth; deepth = INT_MAX; backTracking(root, 1); return deepth; } };
