题目链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree/
递归方案写出来了,也就是深度遍历方式。
迭代方案没有,也就是广度(层序)遍历方式。写的时候想到的是之前的另一个题目:找树左下角的值( http://aspirer.wang/?p=1643),问题是这个迭代是把所有的节点都遍历一遍,导致没办法计算深度。看了题解才知道要稍微改造下,一次出队一层,也就是遍历一层,而不是一个节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: /* 深度遍历方式: void walk(TreeNode* node, int depth, int &maxDepth) { if (!node) { return ; } depth += 1; if (node->left) { walk(node->left, depth, maxDepth); } if (node->right) { walk(node->right, depth, maxDepth); } if (depth > maxDepth) { maxDepth = depth; } } int maxDepth(TreeNode* root) { int depth = 0, max = 0; walk(root, depth, max); return max; } */ // 广度遍历方式: int maxDepth(TreeNode* root) { int max = 0; TreeNode* p; queue<TreeNode*> q; if (!root) { return max; } q.push(root); while (!q.empty()) { int size = q.size(); while (size > 0) { p = q.front(); q.pop(); size--; if (p->left) { q.push(p->left); } if (p->right) { q.push(p->right); } } max++; } return max; } }; |