leetcode 브러시 트리(3) - 귀속: 두 노드의 최장 경로

1613 단어 leetcode

[LeetCode] Diameter of Binary Tree 두 갈래 나무의 지름


 
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longestpath between any two nodes in a tree. This path may or may not pass through the root.
Example: Given a binary tree  
          1
         / \
        2   3
       / \     
      4   5

 
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
 
이 문제는 우리로 하여금 두 갈래 나무의 직경을 구하게 하였으며, 우리에게 직경이 두 점 사이의 가장 먼 거리라는 것을 알려주었고, 문제의 예에 따라 문제의 뜻을 이해하기 어렵지 않게 하였다.우리는 다시 한 번 예에서 그 두 개의 최장 경로 [4, 2, 1, 3]와 [5, 2, 1, 3]을 자세히 관찰했다. 우리가 한 가지 각도를 바꾸어 보면 사실은 뿌리 결점 1의 좌우 두 자목의 깊이의 합이 아닐까.그러면 우리는 각 결점에 대해 좌우자 나무의 깊이의 합을 구하고 이 값을 하나의 후보 값으로 한 다음에 좌우자 결점에 대해 각각 지름 대 귀속 함수를 호출한다. 이 세 값을 서로 비교하고 가장 큰 값을 취하여 결과를 업데이트한다. 지름이 반드시 뿌리 결점을 거치지 않기 때문에 좌우자 결점에 대해 다시 한 번 계산해야 한다.중복 계산을 줄이기 위해 우리는 해시표로 각 결점과 그 깊이 사이의 반사를 구축한다. 이렇게 하면 어떤 결점의 깊이가 계산되기 전에 다시 계산할 필요가 없다. 코드를 참고하면 다음과 같다.
  
class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return max;
    }
    private int height(TreeNode root){
        if(root == null)
            return 0;
        if(root.left == root.right)
            return 1;
        int left = height(root.left);
        int right = height(root.right);
        max = Math.max(left+right, max);
        return Math.max(left, right) + 1;
    }
}

[이렇게 먼저 행동] [AWS] [초보자] 워드프레스의 블로그 시스템 구축①
[leetcode]111.Minimum Depth of Binary Tree

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage