My leetcode same problem solution
1. Recursion(DFS):
n -- number of nodes
L -- height of tree
Time: O(n)
Space: O(h)
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 | /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree. * @return: An integer */ int maxDepth(TreeNode *root) { // write your code here if(!root) return 0; int left = 1; int right = 1; if(root->left) left = maxDepth(root->left) + left; if(root->right) right = maxDepth(root->right) + right; return (left>right)?left:right; } }; |
2. Iterative solution(BFS):
The deepest node is located at the end of the queue
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 | /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree. * @return: An integer */ int maxDepth(TreeNode *root) { queue<pair<TreeNode*, int> > q; if(!root) return 0; q.push(make_pair(root, 1)); while(!q.empty()){ pair<TreeNode*, int> cur = q.front(); q.pop(); if(cur.first->left) q.push(make_pair(cur.first->left, cur.second+1) ); if(cur.first->right) q.push(make_pair(cur.first->right, cur.second+1) ); if(q.empty()) return cur.second; } } }; |
没有评论:
发表评论