666.경로 와 IV

ID:666 TITLE:경로 와 IV TAG:Java,Python,DFS
방법 1:나무 로 변환[Accepted]
배열 이 지정 한 데 이 터 를 트 리 로 만 듭 니 다.그리고 뿌리 노드 에서 모든 잎 결점 까지 의 경로 의 합 을 계산 하면 답 을 얻 을 수 있다.
알고리즘:

은 두 단계 로 나 뉘 는데 구조 수 와 나 무 를 옮 겨 다 닌 다.

나무의 구조 과정 에서 우 리 는 깊이,위치 와 가중치 등 정 보 를 가지 고 우 리 는 조건 pos - 1 < 2*(depth - 2) 에 따라 결점 이 오른쪽 인지 왼쪽 인지 판단 할 수 있다.예 를 들 어 depth = 4 일 때 pos 은 1, 2, 3, 4, 5, 6, 7, 8 을 취 할 수 있 고 pos<=4 일 때 결점 의 위 치 는 왼쪽 에 있다.

을 옮 겨 다 니 는 과정 에서 우 리 는 깊이 있 는 검색 정책 을 실행 하여 트 리 를 옮 겨 다 니 며 우리 가 걸 어 온 경 로 를 따라 현재 와 현재 의 경 로 를 기록 합 니 다.우리 가 잎 결점 (node.left == null && node.right == null) 에 도착 할 때마다 이 경로 의 것 과 답 에 추가 합 니 다.

class Node(object):
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

class Solution(object):
    def pathSum(self, nums):
        self.ans = 0
        root = Node(nums[0] % 10)

        for x in nums[1:]:
            depth, pos, val = x/100, x/10 % 10, x % 10
            pos -= 1
            cur = root
            for d in xrange(depth - 2, -1, -1):
                if pos < 2**d:
                    cur.left = cur = cur.left or Node(val)
                else:
                    cur.right = cur = cur.right or Node(val)

                pos %= 2**d

        def dfs(node, running_sum = 0):
            if not node: return
            running_sum += node.val
            if not node.left and not node.right:
                self.ans += running_sum
            else:
                dfs(node.left, running_sum)
                dfs(node.right, running_sum)

        dfs(root)
        return self.ans

class Solution {
    int ans = 0;
    public int pathSum(int[] nums) {
        Node root = new Node(nums[0] % 10);
        for (int num: nums) {
            if (num == nums[0]) continue;
            int depth = num / 100, pos = num / 10 % 10, val = num % 10;
            pos--;
            Node cur = root;
            for (int d = depth - 2; d >= 0; --d) {
                if (pos < 1<

복잡 도 분석

시간 복잡 도:O(N)O(N)O(N).이 가운데 N N N 은 nums 길이 다.

공간 복잡 도:O(N)O(N)O(N),깊이 는 중 은 식 호출 스 택 의 크기 를 우선 검색 합 니 다.

방법 2:직접 옮 겨 다 니 기[수락]
알고리즘:방법 1 에서 트 리 에서 깊이 우선 검색 을 할 것 입 니 다.시간 을 절약 하 는 생각 은 우리 가 등식 root = num / 10 = 10 * depth + pos 에 따라 뿌리 노드 의 유일한 식별 자 라 는 것 이다.왼쪽 노드 의 식별 자 는 left = 10 * (depth + 1) + 2 * pos - 1 이 고 오른쪽 노드 는 right = left + 1 이다.

class Solution(object):
    def pathSum(self, nums):
        self.ans = 0
        values = {x / 10: x % 10 for x in nums}
        def dfs(node, running_sum = 0):
            if node not in values: return
            running_sum += values[node]
            depth, pos = divmod(node, 10)
            left = (depth + 1) * 10 + 2 * pos - 1
            right = left + 1

            if left not in values and right not in values:
                self.ans += running_sum
            else:
                dfs(left, running_sum)
                dfs(right, running_sum)

        dfs(nums[0] / 10)
        return self.ans

class Solution {
    int ans = 0;
    Map values;
    public int pathSum(int[] nums) {
        values = new HashMap();
        for (int num: nums)
            values.put(num / 10, num % 10);

        dfs(nums[0] / 10, 0);
        return ans;
    }

    public void dfs(int node, int sum) {
        if (!values.containsKey(node)) return;
        sum += values.get(node);

        int depth = node / 10, pos = node % 10;
        int left = (depth + 1) * 10 + 2 * pos - 1;
        int right = left + 1;

        if (!values.containsKey(left) && !values.containsKey(right)) {
            ans += sum;
        } else {
            dfs(left, sum);
            dfs(right, sum);
        }
    }
}

복잡 도 분석

시간 복잡 도:O(N)O(N)O(N).

공간 복잡 도:O(N)O(N)O(N),분석 과 방법 1 이 같다.