Leetcode563. 두 갈래 나무의 경사도

7158 단어 Leetcodeleetcode

Leetcode563. 두 갈래 나무의 경사도


제목: 두 갈래 나무를 정해 전체 나무의 경사도를 계산한다.하나의 트리의 노드의 경사도 정의는 이 노드의 왼쪽 트리의 결점과 오른쪽 트리의 결점의 합차의 절대값이다.빈 결점의 경사도는 0이다.전체 나무의 경사는 모든 노드의 경사의 합이다.
 :

 :
         1
       /   \
      2     3
 :1
 :
  2  : 0
  3  : 0
  1  : |2-3| = 1
  : 0 + 0 + 1 = 1

문제:
  • 변수sum=0을 먼저 정의합니다
  • 두 갈래 나무를 순서대로 훑어본 다음에 왼쪽 노드와 오른쪽 노드의 절대값을 구하고sum에 누적하여 왼쪽 노드가 비어 멈출 때까지 한다.java 코드:
  •   /** 
         * @param root
         * @return
         */
        public static int findTilt(TreeNode root) {
            int sum = 0;
            if (root == null) return 0;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                int s1 = 0, s2 = 0;
                if (node.left != null) {
                    s1 = node.left.value;
                    queue.add(node.left);
                }
                if (node.right != null) {
                    s2 = node.right.value;
                    queue.add(node.right);
                }
                int tmp = Math.abs(s1 - s2);
                sum += tmp;
            }
            return sum;
        }
    
    
    
        static int tilt;
    
        /**
         *  
         * @param root
         * @return
         */
        public static int findTilt2(TreeNode root) {
            if (root == null) return 0;
            int leftSum = findTilt2(root.left);
            int rightSum = findTilt2(root.right);
            tilt += Math.abs(leftSum - rightSum);
            return leftSum + rightSum + root.value;
        }
    

    좋은 웹페이지 즐겨찾기