leetcode系列104-二叉树的最大深度

【题目概述】 104. Maximum Depth of Binary Tree Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children. Example:

Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7

return its depth = 3.

【思路分析】

注意自顶向下递归，传递参数进入函数中，相当于尾递归的形式注意自底向上递归，通过子节点来计算父节点

【代码示例1】

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int maxDepth(struct TreeNode* root){ if(!root) { return 0; } else if(root->left == NULL && root->right == NULL) { return 1; } else { //先从root开始，一直往左边去找，左边又可以被分为左右两边 int leftcount = maxDepth(root->left)+1; int rightcount = maxDepth(root->right)+1; return leftcount>rightcount?leftcount:rightcount; } } [说明]既可以将A,B当做相对独立的执行函数，执行完A后，才能去执行B，又可以将其都看作A或B的子函数 A——int leftcount = maxDepth(root->left)+1; B——int rightcount = maxDepth(root->right)+1;

【代码示例2】

【说明】相当于在做前序遍历，只是多了每次叶子节点的值维护和更新 int maxdepth = 0; void dfs(struct TreeNode *root, int depth) { if(root == NULL) return; if(!root->left && !root->right) { maxdepth = maxdepth>depth?maxdepth:depth; } dfs(root->left, depth+1); dfs(root->right, depth+1); } int maxDepth(struct TreeNode* root){ if(!root) return 0; maxdepth = 1; dfs(root, 1); return maxdepth; }