155. 두 갈래 나무의 최소 깊이

2388 단어
묘사
두 갈래 나무를 정해서 가장 작은 깊이를 찾아라.두 갈래 나무의 최소 깊이는 뿌리 노드에서 가장 가까운 잎 노드까지의 거리이다
예제
다음과 같은 두 갈래 나무를 제시한다.
        1    
     /     \ 
    2       3
          /    \
         4      5  

이 두 갈래 나무의 최소 깊이는 2이다

코드

    /**
     * Definition of TreeNode:
     * public class TreeNode {
     *     public int val;
     *     public TreeNode left, right;
     *     public TreeNode(int val) {
     *         this.val = val;
     *         this.left = this.right = null;
     *     }
     * }
     */
  • 분치+귀속
  •     public class Solution {
            /*
             * @param root: The root of binary tree
             * @return: An integer
             */
            public int minDepth(TreeNode root) {
                int mindepth = helper(root);
                return mindepth;
            }
            
            private int helper(TreeNode root) {
                if (root == null) {
                    return 0;
                }
                
                int leftMinDepth = helper(root.left);
                int rightMinDepth = helper(root.right);
                
                //                     
                //          0,        ,      1
                if (leftMinDepth == 0 || rightMinDepth == 0) {
                    return Math.max(leftMinDepth, rightMinDepth) + 1;
                }
                int min_depth = Math.min(leftMinDepth, rightMinDepth) + 1;
                
                return min_depth;
            }
        }
    
  • 스트리밍+귀속
  •     public class Solution {
            /*
             * @param root: The root of binary tree
             * @return: An integer
             */
             
            private int depth = Integer.MAX_VALUE;
            public int minDepth(TreeNode root) {
                if (root == null) {
                    return 0;
                }
                
                traversal(root, 1);
                return depth;
            }
            
            private void traversal(TreeNode node, int curDepth) {
                //         ,              
                if (node == null) {
                    return;
                }
                
                if (node.left == null && node.right == null) {
                    if (curDepth < depth) {
                        depth = curDepth;
                    }
                }
                
                traversal(node.left, curDepth + 1);
                traversal(node.right, curDepth + 1);
            }
        }
    

    좋은 웹페이지 즐겨찾기