Java 2 O(n) solution, dfs / bfs


  • 0
    M
    1. DFS:
      Time complexity: O(n)
      Space complexity:O(n), worst case only one branch
        
        //dfs
        private int maxDepth_dfs(TreeNode root){
            return dfs(root);
        }
        private int dfs(TreeNode root){
            if(root == null) return 0;
            int depth_l = 0, depth_r = 0;
            if(root.left != null) depth_l = dfs(root.left);
            if(root.right != null) depth_r = dfs(root.right);
            return Math.max(depth_l, depth_r)+1;
        }
    
    1. BFS:
      Time complexity: O(n)
      Space complexity:O(n/2), worst case: complete binary tree
        // bfs
        private int maxDepth_bfs(TreeNode root){
            if(root == null) return 0;
            int depth = 0, curSize = 0;
            Queue<TreeNode> que = new LinkedList<>();
            TreeNode node = root;
            que.offer(node);
            while(!que.isEmpty()){
                curSize = que.size();
                for(int i=0; i<curSize; i++){
                    node = que.poll();
                    if(node.left != null){
                        que.offer(node.left);
                    }
                    if(node.right != null){
                        que.offer(node.right);
                    }
                }
                depth++;
            }
            return depth;
        }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.