이진 트리의 나머지 합계

Question

흥미로운 알고리즘 문제가 있습니다. 우리는 잎과 떨어져있는 모든 정점에서 값 0을 가지는 이진 트리를받습니다. 잎에서 우리는 두 가지 옵션이 있습니다

1. 값을 알 수없는,하지만 우리는> = 1 개

2. 값이 알려져 자연수 알고는 자연수> = 1

입니다

문제는 주어진 트리의 모든 하위 트리가 왼쪽 및 오른쪽 하위 트리의 정점에 동일한 값 합계를 갖도록 잎의 모든 알 수없는 값을 설정할 수 있는지 결정하는 것입니다. 모든 물음표가 자연수이어야한다 고려, 그것은 물론입니다 불가능

-

 0 
    /\ 
    0 ? 
/\ 
    0 5 
/\ 
? ? 

대답은 NO :

트리 1 : 예를 들어

tree2 :

 0 
    / \ 
    0  0 
/\ /\ 
    0 10 ? ? 
/\ 
5 ? 

대답은 예 - 모든 물음표에 각각 5, 10, 10을 설정합니다.

지금까지 나는 명백한 알고리즘 만 제시했습니다. 우리는 선형 방정식의 시스템을 만들고 그것이 자연수의 해를 가졌는지 확인합니다. 그러나 나는 그것이 큰 나무에서 매우 느릴 수 있다고 생각하고 그것을 해결하는 더 좋은 방법이어야합니다. 아무도 도와 줄 수 있니? 나는 매우 감사하게 될 것입니다.

Answer 1

재귀적인 솔루션은 잘 작동한다고 생각합니다. 모든 노드에서 왼쪽과 오른쪽 자식의 무게를 얻습니다.

1. L과 R 모두 알려져있다 : 다음과 같은 경우이 노드가 유효 IFF의 L == R
2. 어느 L 또는 R이 알려져있다 :이 노드를 알 수없는 두 배의 그 다양성 있다 L과 R의 최대 다중도
3. L 또는 R 중 하나만 알 수 있습니다.이 노드는 알려진 자식의 가중치가 알 수없는 자식의 배수로 나눌 수있는 경우 유효합니다. 무게는 알려진 아동의 두 배입니다.

여기서 아이디어는 값이 정수일 수 있기 때문에 알 수없는 자식 노드가 특정 노드 아래에 있는지 추적해야한다는 것입니다. 한 노드에서 왼쪽 자식이 4 개의 알 수없는 노드를 갖고 있고 그 오른쪽에 1 개의 알 수없는 노드가 있어도 1 개의 알 수는 4의 배수 여야하므로이 노드의 다중성은 8이어야하기 때문에 다중성은 항상 두 배가됩니다.

참고 : 여기서 다중성이라는 단어를 사용하고 있으며 실제로는별로 좋지 않지만 사용할 좋은 단어는 생각할 수 없습니다. 당신은 항상 코드 블록에 트리를 그리는 시도 할 수

package main 

import (
    "fmt" 
) 

// Assume that (Left == nil) == (Right == nil) 
type Tree struct { 
    Val   int 
    Left, Right *Tree 
} 

func (t *Tree) GetWeight() (weight int, valid bool) { 
    if t.Left == nil { 
    return t.Val, true 
    } 
    l, lv := t.Left.GetWeight() 
    r, rv := t.Right.GetWeight() 
    if !lv || !rv { 
    return 0, false 
    } 
    if l < 0 && r < 0 { 
    if l < r { 
     return 2 * l, true 
    } 
    return 2 * r, true 
    } 
    if l < 0 { 
    return 2 * r, r%(-l) == 0 
    } 
    if r < 0 { 
    return 2 * l, l%(-r) == 0 
    } 
    return r + l, r == l 
} 

func main() { 
    t := Tree{0, 
    &Tree{0, 
     &Tree{0, 
     &Tree{Val: 5}, 
     &Tree{Val: -1}, 
     }, 
     &Tree{Val: 10}, 
    }, 
    &Tree{0, 
     &Tree{Val: -1}, 
     &Tree{Val: -1}, 
    }, 
    } 
    w, v := t.GetWeight() 
    fmt.Printf("%d, %t\n", w, v) 
    t = Tree{0, 
    &Tree{0, 
     &Tree{0, 
     &Tree{Val: -1}, 
     &Tree{Val: -1}, 
     }, 
     &Tree{Val: 5}, 
    }, 
    &Tree{Val: -1}, 
    } 
    w, v = t.GetWeight() 
    fmt.Printf("%d, %t\n", w, v) 
} 

Answer 2

이것은 병렬 처리가 가능합니다. 잎으로부터 루트쪽으로 방정식의 시스템을 생성하여 각 정점에서 방정식 (및 계산)을 병합합니다. 방정식 시스템이 불가능 해지면 모든 계산을 중단합니다.

이 비평 행 아날로그는 단락 회로 평가 일 것입니다.