牛客在线编程101-BM28 二叉树的最大深度

川长思鸟来 2023-10-04 20:10 4阅读 0赞

描述  
求给定二叉树的最大深度，  
深度是指树的根节点到任一叶子节点路径上节点的数量。  
最大深度是所有叶子节点的深度的最大值。  
（注：叶子节点是指没有子节点的节点。）

数据范围：0 \\le n \\le 1000000≤n≤100000，树上每个节点的val满足 |val| \\le 100∣val∣≤100  
要求： 空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)

用三种方法解题  
递归

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */
    
    public class Solution {
        
        /**
         * 
         * @param root TreeNode类 
         * @return int整型
         */
        public int maxDepth (TreeNode root) {
        
            // write code here
            return root == null ? 0 : (Math.max(maxDepth(root.left), maxDepth(root.right)) + 1);
        }
    }

BFS

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */
    
    public class Solution {
        
        /**
         *
         * @param root TreeNode类
         * @return int整型
         */
        public int maxDepth (TreeNode root) {
        
            // write code here
            int max = 0;
    
            if (root == null) {
        
                return 0;
            }
    
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.add(root);
    
            while (!q.isEmpty()) {
        
                max++;
                int n = q.size();
                for (int i = 0; i < n; i++) {
        
                    TreeNode cur = q.poll();
                    if (cur.left != null) {
        
                        q.add(cur.left);
                    }
                    if (cur.right != null) {
        
                        q.add(cur.right);
                    }
                }
            }
            return max;
        }
    }

DFS

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */
    
    public class Solution {
        
        /**
         *
         * @param root TreeNode类
         * @return int整型
         */
        int max = 0;
    
        public int maxDepth (TreeNode root) {
        
            // write code here
            if (root == null) {
        
                return 0;
            }
    
            TreeNode cur = root;
            dfs(root, 0);
            return max;
        }
    
        public void dfs(TreeNode cur, int depth) {
        
            if (cur == null) {
        
                max = Math.max(max, depth);
                return;
            }
            dfs(cur.left, depth + 1);
            dfs(cur.right, depth + 1);
        }
    }