[LeetCode] 104. Maximum Depth of Binary Tree

轉自LeetCode

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>

這題是滿典型用 DFS 的題目，在 traversal 的過程，順便紀錄最大深度即可

code 如下
c++

	/**
	* 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 {
	private:
	int ans;
	public:
	int maxDepth(TreeNode* root) {
	ans = 0;
	if(!root) {
	return ans;
	}
	dfs(root, 0);
	return ans;
	}
	void dfs(TreeNode *node, const int &depth) {
	if(node == NULL) {
	ans = max(ans, depth);
	return;
	}
	dfs(node->left, depth+1);
	dfs(node->right, depth+1);
	}
	};

view raw maxDepthOfBinaryTree_1.cpp hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun maxDepth(root: TreeNode?): Int {
	return dfs(root, 0)
	}
	fun dfs(node: TreeNode?, depth: Int): Int {
	return if(node == null) {
	depth
	} else {
	Math.max(dfs(node!!.left, depth+1), dfs(node!!.right, depth+1))
	}
	}
	}

view raw maximum_depth_of_binary_tree.kt hosted with ❤ by GitHub

還有一個比較慢的解法，就是用 level order traversal

當所有 level 都走過之後，就會知道樹的最大深度是多少了

code 如下

	/**
	* 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) {
	int ans = 0;
	if(!root) {
	return ans;
	}
	queue<TreeNode *> nodeQue;
	nodeQue.push(root);
	//> level order traversal
	while(!nodeQue.empty()) {
	++ans;
	int size = nodeQue.size();
	for(int i = 0; i < size; i++) {
	TreeNode *tmpNode = nodeQue.front();
	nodeQue.pop();
	if(tmpNode->left) {
	nodeQue.push(tmpNode->left);
	}
	if(tmpNode->right) {
	nodeQue.push(tmpNode->right);
	}
	}
	}
	return ans;
	}
	};

view raw maxDepthOfBinaryTree_2.cpp hosted with ❤ by GitHub