leetcode: Maximum Depth of Binary Tree

Problem Description:

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.

Solution and Precautions:

Way1: DFS to traverse the whole tree and use a variable to keep the current maximum depth, when encountering a deeper one, update the maximum depth. The accepted code is as follows:

class Solution {
public:
    void dfs(TreeNode *root, int depth, int *pmaxDepth) {
                if (NULL == root->left && NULL == root->right) 
			*pmaxDepth = (depth > *pmaxDepth) ? depth : *pmaxDepth;
		if (root->left) dfs(root->left, depth + 1, pmaxDepth);
		if (root->right) dfs(root->right, depth + 1, pmaxDepth);
    }

    int maxDepthInner2(TreeNode *root) {
		if (NULL == root) return 0;
		int maxDepth = 0;
		dfs(root, 1, &maxDepth); 
		return maxDepth;
    }

    int maxDepth(TreeNode *root) {
		return maxDepthInner2(root);
    }
};

Way 2: Or maybe a simpler way is just use recursive method without the explicit depth variable:

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

Tips and Divergent thinking:

(1) The above simple code of Way 2 works efficiently because it is a tree rather than a graph, so we don’t have to manually keep some explicit intermediate depth variable as in DP.
(2) The code of Way 1 looks more tedious than that of way 2, however it is more generalized, we can easily modify the code to deal with other thing when we reach a leaf node, such as finding the minimum depth of binary tree! This cannot be easily done by simply modifying the code in Way 1.

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on April 20, 2013