This is the 22nd day of my participation in Gwen Challenge

Maximum depth of binary tree (104)

Topic describes

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.

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

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns its maximum depth of 3.

Thought analysis

To find the maximum depth of the binary tree, we can use a recursive solution to decompose the large problem into subproblems, that is, into the maximum depth of the left subtree and the maximum depth of the right subtree. For each layer of depth, we increment by 1, and then decompose layer by layer until root == null.

For the maximum depth of the binary tree, we can use a recursive solution to decompose the large problem into subproblems, that is, into the maximum depth of the left subtree and the maximum depth of the right subtree. For each layer of depth, we add 1 by ourselves, and then decompose layer by layer until root == null.

The code shown

Solution a:

public int maxDepth(TreeNode root) {
        if(root == null) {return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
Copy the code

Maximum depth of n-tree (559)

Topic describes

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.

N fork tree input is serialized in sequential traversal, with each set of child nodes separated by null values (see example).

Example 1:

Input: root = [1,null,3,2,4,null,5,6] output: 3Copy the code

Example 2:

Input: root = [1, null, 2, 5-tetrafluorobenzoic, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14] output: 5Copy the code

prompt

  • The height of an n-tree is less than or equal to1000
  • The total number of nodes is in range[0, 10 ^ 4) 内

Thought analysis

N, maximum depth of fork tree method and the maximum depth of a binary tree is very similar, we put the N fork a node of the tree of traverse all his children, in the same way we can be a big problem is decomposed into small problems, that is to find out the root node of the maximum depth of all the child nodes of the node, all problem can be broken, until the node is empty.

The code shown

Solution a:

private int deep;
    public int maxDepth(Node root) {
        if(root == null) {return 0;
        } else if(root.children.isEmpty()){
            return 1;
        } else {
            List<Integer> heights = new LinkedList<>();
            for(Node node: root.children){
                heights.add(maxDepth(node));
            }
            return Collections.max(heights) + 1; }}Copy the code

conclusion

Binary tree with N fork tree can use recursion to solve many problems of, as for how to use recursion, the key lies in how to resolve the big problem to small problems, at the same time, problem solution and small is the same, the solution to the problem, of course, recursive termination condition is also very important, based on the above steps are decomposed, the answer we can quickly to solve similar problems.

Because recursion and our brain ideas are not so similar, so the solution of the recursion problem is to clarify the ideas, have an overall grasp in the macro, from large to small, complex to simple, in order to do a good job in the relevant topic.