Skip to content

Latest commit

 

History

History
310 lines (263 loc) · 6.03 KB

104.maximum-depth-of-binary-tree.en.md

File metadata and controls

310 lines (263 loc) · 6.03 KB

Problem (104. The maximum depth of the binary tree)

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

Title description

Given a binary tree, find its maximum depth. The depth of a binary tree is the number of nodes on the longest path from the root node to the farthest leaf node. Description: Leaf nodes refer to nodes without child nodes. example： Given a binary tree [3,9,20, null,null,15,7]， 3 / \ 9 20 / \ 15 7 Return to its maximum depth of 3.

Pre-knowledge

-recursion

Company

-Ali -Tencent -Baidu -Byte

  • apple
  • linkedin
  • uber
  • yahoo

Idea

Since a tree is a recursive data structure, it is often very easy to solve recursively, and this problem happens to be the same.，

-The code implemented recursively is as follows：

varmaxDepth=function(root){if(!root)return0;if(!root.left&&!root.right)return1;return1+Math.max(maxDepth(root.left),maxDepth(root.right));};

What if iteration is used? The first thing we should think of is the various traversals of the tree. Since we are looking for depth, we should think of various traversals of the tree. It is very appropriate to use hierarchical traversal (BFS). We only need to record how many layers there are. For related ideas, please check binary-tree-traversal

Analysis of key points

-Queue -Use Null (a special element) in the queue to divide each layer, or save the number of current queue elements (that is, the number of elements contained in the current layer) before iterating over each layer. -Basic operation of tree-Traversal-hierarchical traversal (BFS)

Code

-Language support: JS, C++, Java, Python, Go, PHP

JS Code:

/** @lc app=leetcode id=104 lang=javascript** [104] Maximum Depth of Binary Tree*//*** Definition for a binary tree node.* function TreeNode(val) {* this. val = val;* this. left = this. right = null;* }*//*** @param {TreeNode} root* @return {number}*/varmaxDepth=function(root){if(!root)return0;if(!root.left&&!root.right)return1;// Hierarchical traversal BFSletcur=root;constqueue=[root,null];letdepth=1;while((cur=queue.shift())!==undefined){if(cur===null){// Note️️: If not processed, it will loop infinitely, and the stack will overflow.if(queue.length===0)returndepth;depth++;queue.push(null);continue;}constl=cur.left;constr=cur.right;if(l)queue.push(l);if(r)queue.push(r);}returndepth;};

C++ Code:

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/classSolution { public:intmaxDepth(TreeNode* root) { if (root == nullptr) return0; auto q = vector<TreeNode*>(); auto d = 0; q. push_back(root); while (! q. empty()) { ++d; auto sz = q. size(); for (auto i = 0; i < sz; ++i) { auto t = q. front(); q. erase(q. begin()); if (t->left ! = nullptr) q. push_back(t->left); if (t->right ! = nullptr) q. push_back(t->right); } } return d; } };

Java Code:

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/classSolution { publicintmaxDepth(TreeNoderoot) { if(root == null) { return0; } // QueueQueue<TreeNode> queue = newLinkedList<TreeNode>(); queue. offer(root); intres = 0; // Expand by layerwhile(! queue. isEmpty()) { // Take out all the nodes in this layer and press them into the child nodesintsize = queue. size(); while(size > 0) { TreeNodenode = queue. poll(); if(node. left ! = null) { queue. offer(node. left); } if(node. right ! = null) { queue. offer(node. right); } size-=1; } // Number of statistical layersres +=1; } returnres; } }

Python Code:

classSolution: defmaxDepth(self, root: TreeNode) ->int: ifnotroot: return0q, depth= [root, None], 1whileq: node=q. pop(0) ifnode: ifnode. left: q. append(node. left) ifnode. right: q. append(node. right) elifq: q. append(None) depth+=1returndepth

Go Code:

/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/// BFSfuncmaxDepth(root*TreeNode) int { ifroot==nil { return0 } depth:=1q:= []*TreeNode{root, nil} // queuevarnode*TreeNodeforlen(q) >0 { node, q=q[0], q[1:] // popifnode!=nil { if node. Left!=nil { q=append(q, node. Left) } if node. Right!=nil { q=append(q, node. Right) } } Elseiflen(q)>0 {// Pay attention to determine whether there is only one nil in the queueq=append(q, nil) depth++ } } returndepth }

PHP Code:

/*** Definition for a binary tree node.* class TreeNode {* public $val = null;* public $left = null;* public $right = null;* function __construct($value) { $this->val = $value; }* }*/class Solution { /*** @param TreeNode $root* @return Integer*/functionmaxDepth($root) { if (! $root) return0; $depth = 1; $arr = [$root, null]; while ($arr) { /** @var TreeNode $node */$node = array_shift($arr); if ($node) { if ($node->left) array_push($arr, $node->left); if ($node->right) array_push($arr, $node->right); } elseif ($arr) { $depth++; array_push($arr, null); } } return$depth; } }

Complexity analysis

-Time complexity:$O(N)$ -Spatial complexity:$O(N)$

Related topics

If you have any comments on this, please leave me a message. I will check the answers one by one when I have time. For more algorithm routines, you can visit my LeetCode problem solving warehouse:https://github.com/azl397985856/leetcode . There are already 37K stars. You can also pay attention to my public account "Force Buckle Plus" to take you to chew off the hard bone of the algorithm.

close