2013-06-10 4 views
11

다음은 내 코드에서 수행해야하는 작업입니다.재귀 이진 검색 트리 x = 변경 (x)

Before Call: 
      +----+ 
      | -9 | 
      +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 3 |  | 15 | 
     +----+  +----+ 
    /  / \ 
    /  /  \ 
+----+  +----+  +----+ 
| 0 |  | 12 |  | 24 | 
+----+  +----+  +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 6 |  | -3 | 
     +----+  +----+ 

After Call: 
      +----+ 
      | -9 | 
      +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 6 |  | 30 | 
     +----+  +----+ 
    /  / \ 
    /  /  \ 
+----+  +----+  +----+ 
| 0 |  | 24 |  | 48 | 
+----+  +----+  +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 12 |  | -3 | 
     +----+  +----+ 

기본적으로이 문제는 정수의 이진 트리에서 0보다 큰 모든 데이터 값을 두 배로해야합니다. 아래 코드는 몇 가지 값에 대해 이렇게하지만 일찍 중지합니다. 이 재귀 적으로 수정하는 방법을 모르겠습니다. 이것은 위에 주어진 트리에 대한 내 결과물과 같습니다.

 overallRoot 
     _[-9]_______________ 
     /     \ 
    _[6]     _____[30] 
/    /  \ 
[0]    _[12]   [24] 
       / \ 
       [6]  [-3] 
public void doublePositives() { 
    doublePositives(overallRoot); 
} 

private IntTreeNode doublePositives(IntTreeNode root) { 
    if(root != null) { 
     if(root.data > 0) { 
      root.data = 2* root.data; 
     }else { 
      root.left = doublePositives(root.left); 
      root.right= doublePositives(root.right); 
     } 
    } 
    return root; 
} 
+4

+1! – arynaq

답변

4

노드를 두 배로 늘리려면 트리를 계속 트래버스해야합니다. 항상 트래버스하도록 else을 버리십시오.

if(root.data > 0) { 
     root.data = 2* root.data; 
    }else { 
     root.left = doublePositives(root.left); 
     root.right= doublePositives(root.right); 
    } 

경우] : - 당신은 부정적인 노드의 아이의 두 배 값

if(root != null) { 
    if(root.data > 0) { 
     root.data = 2 * root.data; 
    } 
    doublePositives(root.left); 
    doublePositives(root.right); 
} 
+0

나는 본다! 고마워요. 지금이 문제를 이해합니다. :) – this1lefty

2

루트가 양수이면 재귀 호출을 수행하지 않습니다.

루트가 음수 일 때만 재귀 호출을 수행합니다. 이 문제를 해결하려면 else를 제거하십시오.

private IntTreeNode doublePositives(IntTreeNode root) { 
    if(root != null) { 
     if(root.data > 0) { 
      root.data = 2* root.data; 
     } 
     root.left = doublePositives(root.left); 
     root.right= doublePositives(root.right); 
    } 
    return root; 
} 
+0

감사합니다. 나는 나의 실수를 본다 – this1lefty

5

는 논리 문제처럼 보이는 : 또한, 당신이 트리 구조를 변경하지 않기 때문에 할당을 제거했습니다 루트 값은 양수입니다. 루트에 도달하지 못합니다. & root.right. 당신은 조건문에서 실수를했다 :

if(root.data > 0) { 
     root.data = 2* root.data; 
    } 
    root.left = doublePositives(root.left); 
    root.right= doublePositives(root.right); 
+0

감사합니다. :) – this1lefty

3

이 시도 : 이런 식으로 뭔가가 더 좋을 것이다. 이것은 이와 같이 작성되었을 것입니다. 루트에 데이터가 양수인 경우 - 두 배로 만듭니다. 그리고 밖으로! 다음 단계에서 왼쪽 및 오른쪽 하위 노드를 진행합니다.

또한이 점에 유의하여 재귀 함수 doublePositives()에서 아무것도 (공백 제외)를 반환 할 필요가 없습니다.

public void iWillDoit() { 
     doublePositives(Root); 
    } 

    private void doublePositives(IntTreeNode root) { 
     if(root != null) { 
      if(root.data > 0) 
      { 
       root.data = 2* root.data; 
      } 
      doublePositives(root.left); 
      doublePositives(root.right);  
     } 
    } 
+0

고마워요! – this1lefty