The article directories

    • Problem: 104. Maximum depth of binary trees
      • The recursive method
        • Recursion in three steps
        • Recursive algorithm (post-order traversal)
        • Iterative method (post-sequential iteration)
      • Iterative method (this is a layer by layer calculation of height, preferably with a sequence traversal)
    • Problem: 559. Maximum depth of N fork tree
        • Recursion, backward traversal
        • Iterative method (post-sequential traversal)
        • Iterative method, sequence traversal
    • Question: 111. The minimum depth of binary trees
      • The recursive method
        • Recursive trilogy
        • Recursive algorithm, post – order traversal
        • Iterative method, sequence traversal

Problem: 104. Maximum depth of binary trees

Given a binary tree, find its maximum depth.

The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

Note: Leaf nodes are nodes that have no child nodes.

Example: given a binary tree [3,9,20,null,null,15,7],

Returns its maximum depth of 3.

The recursive method

Recursion in three steps

The height of the tree is calculated by the return value of the recursive function.

Follow the recursive trilogy to see how to write it.

Determine the argument and return value of the recursive function: the argument is the root node of the passed tree, and the return value is the depth of the tree, so the return value is int. The code is as follows:

int getDepth(TreeNode* node)

Determine the termination condition: if the node is empty, return 0, indicating a height of 0. The code is as follows:

if (node == NULL) return 0;

Determine the logic of single-layer recursion: first find the depth of its left subtree, then find the depth of its right subtree, and finally take the maximum value of left and right depth and then +1 (plus 1 because the current middle node is included) is the depth of the tree where the current node is the root node. The code is as follows :(after traversal, in the order of left and right)

int leftDepth = getDepth(node->left); Left int rightDepth = getDepth(node->right); // rightDepth = 1 + Max (leftDepth, rightDepth); // Return depth;

Recursive algorithm (post-order traversal)

So the overall code is as follows:

class Solution {
    public int maxDepth(TreeNode root) {
      if (null == root) return0; int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); int depth = 1+Math.max(leftDepth,rightDepth); // After the order traversal, left and right, each time in the middle operation to calculate the depthreturndepth; }}Copy the code

So I’m going to do it again using the same template iterative way of doing a post-loop, a while loop, but it’s hard to write, but it works

Iterative method (post-sequential iteration)

class Solution {
    public int maxDepth(TreeNode root) {
      if (null == root) return0; // null==root checks to prevent null Pointers before threereturn; List<Integer> List =new ArrayList<>(); Stack<TreeNode> Stack =new Stack<>(); stack.push(root); int depth =0; int result =0;while(! stack.isEmpty()){ TreeNode node = stack.peek(); //if(node! =null){ stack.pop(); stack.push(node); stack.push(null); depth++;if(node.right ! =null)stack.push(node.right); / / this oneifMake sure not to insert a null and not to insert a null pointer exception when retrieving Node. valif(node.left ! =null) stack.push(node.left); }else{ stack.pop(); node = stack.pop(); depth--; } result = Math.max(result,depth); // take the maximum}returnresult; }}Copy the code

Iterative method (this is a layer by layer calculation of height, preferably with a sequence traversal)

Using the iterative method, the sequential traversal is the most appropriate, because the maximum depth is the number of levels of the binary tree, which is very consistent with the sequential traversal.

So the iteration method of this problem is a template problem, which can be solved by using the template of binary tree sequence traversal. The code is as follows:

class Solution {
    public int maxDepth(TreeNode root) {
      if (null == root) return0; Queue<TreeNode> queue=new LinkedList<>(); int depth=0; Queue.offer (root) is set to 0 because queuewhileIn the loop, depth++ is executed once, so even if there is only one root node, this is guaranteedreturndepth; isreturn 1;
      queue.offer(root);
      while(! queue.isEmpty()){ int size = queue.size(); depth++; / / eachfor(int i=0; i<size; TreeNode node = queue.poll(); TreeNode node = queue.poll(); // The uppermost nodeif(node.left ! = null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);
         }
      }
      returndepth; }}Copy the code

The value is 0 because queue.offer(root) can be inserted into the while loop and depth++ is executed once, so the return depth is guaranteed even if there is only one root node; Is the return 1;

So we can solve the problem of maximum depth of n-tree by the way

Problem: 559. Maximum depth of N fork tree

Given an n-fork tree, find its maximum depth.

The maximum depth is the total number of nodes along the longest path from the root node to the farthest leaf node.

For example, given a 3-fork tree:

The picture

We should go back to its maximum depth, 3.

We can still provide recursive and iterative methods to solve this problem. The idea is the same as the binary tree idea, and the code is directly given as follows:

Recursion, backward traversal

class Solution {
    public int maxDepth(Node root) {
        if (null == root) return 0;
        int max=0;
        for(int i=0; i<root.children.size(); i++){ int depth = maxDepth(root.children.get(i));if(depth > max) max=depth; // get the maximum value}returnmax+1; }}Copy the code

It becomes simpler as follows:

class Solution {
    public int maxDepth(Node root) {
        if (null == root) return 0;
        int depth=0;
        for(int i=0; i<root.children.size(); i++){ depth = Math.max(maxDepth(root.children.get(i)),depth); }returndepth+1; }}Copy the code

Iterative method (post-sequential traversal)

class Solution {
    public int maxDepth(Node root) {
        if (null == root) return0; // null==root checks to prevent null Pointers before threereturn; List<Integer> List =new ArrayList<>(); Stack<Node> Stack =new Stack<>(); stack.push(root); int depth =0; int result =0;while(! stack.isEmpty()){ Node node = stack.peek(); //if(node! =null){ stack.pop(); stack.push(node); stack.push(null); depth++;for(int i=0; i<node.children.size(); i++){if(node.children.get(i)! =null)ifStack. Push (node.children.get(I)); }}else{ stack.pop(); node = stack.pop(); depth--; } result = Math.max(result,depth); // take the maximum}returnresult; }}Copy the code

So depth++ depth– there’s double counting

Iterative method, sequence traversal

It is still the sequence traversal, the code is as follows:

class Solution {
    public int maxDepth(Node root) {
      if (null == root) return0; Queue<Node> queue=new LinkedList<>(); queue.offer(root); int depth=0; Queue.offer (root) is set to 0 because queuewhileIn the loop, depth++ is executed once, so even if there is only one root node, this is guaranteedreturndepth; isreturn 1;
      while(! queue.isEmpty()){ int size = queue.size(); depth++; / / eachfor(int i=0; i<size; i++){ Node node = queue.poll(); // The uppermost nodefor(int j=0; j<node.children.size(); j++){if(node.children.get(j)! =null) queue.offer(node.children.get(j)); }}}returndepth; }}Copy the code

The value is 0 because queue.offer(root) can be inserted into the while loop and depth++ is executed once, so the return depth is guaranteed even if there is only one root node; Is the return 1;

Question: 111. The minimum depth of binary trees

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.

Note: Leaf nodes are nodes that have no child nodes.

Example:

Given a binary tree [3,9,20,null,null,15,7],

Returns its minimum depth of 2.

Train of thought

Look at the maximum depth of these trees, and see how to find the minimum depth. Intuitively, it seems to be the same as finding the maximum depth, but it’s not quite as deep. The traversal order is still post-order traversal (because we need to compare the results after recursive return), but in the logic of processing intermediate nodes, the maximum depth is easy to understand, while the minimum depth may have a misunderstanding, as shown in the figure:

Minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node. , note the “leaf node”.

What is a leaf node? The node where the left and right children are empty is a leaf node!

The recursive method

Recursive trilogy

The first step is to determine the parameters and return values of the recursive function

The argument is the binary root node to pass in and returns the depth of type int.

The code is as follows:

int minDepth(TreeNode root)
Copy the code

The second step is to determine the termination condition. The termination condition also returns 0 when an empty node is encountered, indicating that the height of the current node is 0.

The code is as follows:

if (null == root) return 0;
Copy the code

In the third step, determining the logical part of the single-layer recursion is not the same as finding the maximum depth. Some students may write the following code:

int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
int depth = 1+ Math.min(leftDepth,rightDepth);
return depth;
Copy the code

This code commits the error in this diagram:

If you do that, the branch with no left child will be the shortest depth.

So,

  1. If the left subtree is empty and the right subtree is not, the minimum depth is 1 + the depth of the right subtree.
  2. The right subtree is empty, the left subtree is not empty, and the minimum depth is 1 + the depth of the left subtree.
  3. If the left and right subtrees are not empty, return the minimum depth of the left and right subtrees + 1.

The code is as follows:

int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if(root.left==null && root.right! =null)return 1+rightDepth;
if(root.left! =null && root.right==null)return 1+leftDepth;
int depth = 1+ Math.min(leftDepth,rightDepth);
return depth;
Copy the code

It can be seen that “the difference between finding the minimum depth of the binary tree and finding the maximum depth of the binary tree mainly lies in processing the logic that the left and right children are not empty, which is to add a few more if judgments”.

Recursive algorithm, post – order traversal

The overall recursive code is as follows:

class Solution {
    public int minDepth(TreeNode root) {
        if (null == root) return0; // left int leftDepth = minDepth(root.left); // right int rightDepth = minDepth(root.right); / /if(root.left==null && root.right! =null)return 1+rightDepth;
        if(root.left! =null && root.right==null)return 1+leftDepth;
        int depth = 1+ Math.min(leftDepth,rightDepth);
        returndepth; }}Copy the code

Iterative method, sequence traversal

As opposed to binary trees: look at the maximum depth of these trees. You can also use sequential traversal to solve the problem. Same idea.

If you are not sure about sequence traversal, you can read this article: Binary tree: Sequence traversal comes on!

“It is important to note that the lowest point of the traversal is only when both the left and right children are empty. If one of the children is empty, it is not the lowest point.”

The code is as follows:

class Solution {
    public int minDepth(TreeNode root) {
        if (null == root) return0; Queue<TreeNode> queue = new LinkedList(); int depth=0; Queue.offer (root) is set to 0 because queuewhileIn the loop, depth++ is executed once, so even if there is only one root node, this is guaranteedreturndepth; isreturn 1;
        queue.offer(root);
        while(! queue.isEmpty()){ int size=queue.size(); depth++; int flag=0;for(int i=0; i<size; i++){ TreeNode node = queue.poll();if(node.left! =null) queue.offer(node.left);if(node.right! =null) queue.offer(node.right);if (node.left==null && node.right==null){  
                   flag=1;
                   break; }}if (flag==1)
               break;
        }
        returndepth; }}Copy the code

The value is 0 because queue.offer(root) can be inserted into the while loop and depth++ is executed once, so the return depth is guaranteed even if there is only one root node; Is the return 1;