LeetCode 104. Maximum Depth of Binary Tree

LeetCode 104. Maximum Depth of Binary Tree

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.

Example:

Input: [1,2,3,4,2,4,3]

   1
 2   2
3 4 4 3

Output: 3

---

分析：

首先判断特殊情况，根节点为NULL，即返回0，这也是递归终结的条件；然后分别递归左子树和右子树；注意树的深度需要加上1。

一开始我的代码写得比较冗余，注释里我已标注，后来看了LeetCode上面的Discuss说可以一行搞定，我就发现我可以删掉大部分代码；

LeetCode上面还有使用宽度优先遍历BFS算法解决这道题的，主要利用队列的入队、出队操作，我也尝试自己编写了，代码顺便给出来，在文章末尾。

代码如下：

#include <iostream>
using namespace std;
/**
 * Definition for a binary tree node.
 */
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
	int maxDepth(TreeNode* root) {
		if (root == NULL) {
			return 0;
		}
		// 可以简化
		// else if (root->left == NULL && root->right == NULL) {
		// 	return 1;
		// }
		// else if (root->left != NULL && root->right == NULL) {
		// 	return maxDepth(root->left) + 1;
		// }
		// else if (root->left == NULL && root->right != NULL) {
		// 	return maxDepth(root->right) + 1;
		// }
		else {
			int leftDepth = maxDepth(root->left) + 1;
			int rightDepth = maxDepth(root->right) + 1;
			return leftDepth > rightDepth ? leftDepth : rightDepth;
		}
	}
};
// 构造二叉树
int TreeNodeCreate(TreeNode* &tree) {
	int val;
	cin >> val;
	if (val < 0) // 小于0表示空节点
		tree = NULL;
	else {
		tree = new TreeNode(val); // 创建根节点
		tree->val = val;
		TreeNodeCreate(tree->left); // 创建左子树
		TreeNodeCreate(tree->right);// 创建右子树
	}
	return 0;
}
int main() {
	Solution s;
	TreeNode* tree;
	TreeNodeCreate(tree);
	cout << s.maxDepth(tree) << endl;
	return 0;
}
/*
input:
1
2
3
-1 -1
4
-1 -1
2
4
-1 -1
3
-1 -1

output:
3
 */

One line:

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

宽度优先遍历BFS:

class Solution {
public:
	int maxDepth(TreeNode* root) {
		if (root == NULL) return 0;
		int res = 0;
		queue<TreeNode *> q;
		q.push(root);
		while (!q.empty()) {
			res++;
			int n = q.size();
			for (int i = 0; i < n; i++) {
				TreeNode *p = q.front();
				q.pop();
				if (p->left != NULL) q.push(p->left);
				if (p->right != NULL) q.push(p->right);
			}
		}
		return res;
	}
};