This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

They’re saying, given a binary tree, you want to find the depth from the root node to the farthest leaf node.

For example, you are given a binary tree of 1 / \ 2, 4 / \ 816. The tree has three leaves, 2, 8, 16. The farthest leaf nodes are 8 and 16, and the root node has 3 nodes up to 8 or 16, so the maximum depth is 3.Copy the code


Ii. Analysis of Ideas:

This problem is looking at tree traversal.

Ideas:

  1. Recursive traversal (DFS)
  2. Simulate hierarchical traversal with queues (BFS)


Three,ACCode:

public class LeetCode_104 {
    
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(intx) { val = x; }}// recursive traversal
    // Time: O(n), Space: (n), Faster: 100%
    public int maxDepthWithRecursive(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepthWithRecursive(root.left), 
        maxDepthWithRecursive(root.right)) + 1;
    }

    // Hierarchy traversal, with queue simulation:
    // Time: O(n), Space: (n), Faster: 11.57%
    public int maxDepthWithQueue(TreeNode root) {

        if (root == null) return 0;
        int maxDepth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(! queue.isEmpty()) {int size = queue.size();
            for (int i = 0; i < size; ++i) {

                TreeNode node = queue.poll();
                if(node.left ! =null) queue.add(node.left);
                if(node.right ! =null) queue.add(node.right);
            }
            ++maxDepth;
        }
        returnmaxDepth; }}Copy the code


Iv. Summary:

Tree traversal template

There are four types of tree traversal:

  1. The former sequence traversal
  2. In the sequence traversal
  3. After the sequence traversal
  4. Level traversal

It can also be divided into depth-first traversal (DFS) and breadth-first traversal (BFS)

Hierarchy traversal: Is for breadth-first traversal.

Other traversal: Is for depth-first traversal.

1. Preorder traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    // Preorder traversal code
    
    traverse(root.left);
    traverse(root.right);
}
Copy the code

2. Middle order traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    traverse(root.left);
    
    // Preorder traversal code
    
    traverse(root.right);
}
Copy the code

3. Back-order traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    traverse(root.left);
    traverse(root.right);
    
    // Preorder traversal code
}
Copy the code

4. Hierarchy traversal

Queue simulation

void traverse(TreeNode root) {
    if (null == root) return;
    
    // Initialize the queue to add root to the queue
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    
    while(! q.isEmpty()) { TreeNode cur = q.poll();// Hierarchy traverses code
        System.out.println(root.val);
        
        if(cur.left ! =null) q.offer(cur.left);
        if(cur.right ! =null) q.offer(cur.right); }}Copy the code