104. 二叉树的最大深度

104. 二叉树的最大深度

• 题目
• 算法设计：回溯
• 算法设计：分解子问题

题目

传送门：https://leetcode.cn/problems/maximum-depth-of-binary-tree/

算法设计：回溯

回溯框架，请猛击：《常见递归模式》。

思路：遍历一遍二叉树，用一个外部变量记录每个节点所在的深度，取最大值就可以得到最大深度，这就是遍历二叉树计算答案的思路。

递归函数 = 回溯模式 + 前序位置 + 做某事（选出最大深度）

class Solution {
        int res = 0;
		int depth = 0;  // 记录遍历到的节点的深度
public:
    int maxDepth(TreeNode *root) {
		recall(root);
    	return res;
    }
	
	void recall(TreeNode *root) {
   		if (root == nullptr) 
        	return;
    
    	depth++;
    	res = max(res, depth);
    	recall(root->left);
    	recall(root->right);
    	depth--;
	}
};

算法设计：分解子问题

分解子问题框架，请猛击：《常见递归模式》。

一棵二叉树的最大深度可以通过子树的最大深度推导出来。

递归函数 = 分解子问题模式 + 后序位置 + 做某事【树的深度 = max(左子树最大深度 + 右子树最大深度）+ 根节点自己】

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};