두 갈래 나무의 서브 구조, 깊이 및 두 갈래 나무 재건

카탈로그

두 갈래 나무의 깊이

균형 이차수

두 갈래 나무의 자구조

두 갈래 나무의 재건

요약

참고자료

순서

두 갈래 나무와 관련된 세트는 네 가지 반복 방식을 제외하고 많은 내용이 있다. 두 갈래 나무의 깊이가 있어 하나의 수조를 두 갈래 나무로 구축한다.오늘 이어서 두 갈래 나무를 해치웠다.

두 갈래 나무의 깊이

검지 offer 55-I 문제, Leetcode 104 문제:
두 갈래 나무의 뿌리 노드를 입력하여 이 나무의 깊이를 구하세요.뿌리 노드에서 잎 노드까지 순서대로 지나가는 노드(뿌리, 잎 노드 포함)는 나무의 경로를 형성하고 가장 긴 경로의 길이는 나무의 깊이이다.
예를 들어 두 갈래 나무[3,9,20,null,null,15,7]를 주면 그의 최대 깊이를 되돌려준다.

    3
   / \
  9  20
    /  \
   15   7

두 갈래 나무의 깊이는 말하자면 두 갈래 나무가 몇 층이나 있기 때문에 층계로 두루 훑어볼 수 있고 몇 층이 있는지 통계하면 된다.
레이어 반복 방법 사용하기:

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue queue=new LinkedList<>();
    queue.add(root);
    TreeNode node;
    int dep=1;
    while (!queue.isEmpty()){
        int len=queue.size();
        for (int i=0;i

시간 복잡도: 전체 트리의 노드를 양쪽으로 접근O(n)

공간 복잡도: 상태를 저장하기 위해 창고를 추가로 사용O(n)

층차적으로 훑어보는 것을 제외하고 귀속적인 방법을 고려하여 뿌리 노드에 대해 각각 왼쪽 나무의 깊이와 오른쪽 나무의 깊이를 구하여 그들의 최대치를 취한 다음에 +1이 바로 이 나무의 깊이다.반면 왼쪽 나무와 오른쪽 나무는 다음과 같이 귀속할 수 있다.

public int maxDepth(ThreeNode root){
    // 
    if(root==null) return 0;
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}

시간 복잡도: 모든 나무의 노드를 두루 훑어보았고 O(n) 공간 복잡도: 나무가 단일 사슬로 퇴화되면 귀속의 깊이는 n이기 때문에 공간 복잡도O(n)

평형 두 갈래 나무

균형 두 갈래 나무 정의: 만약에 어떤 두 갈래 나무 중 임의의 노드의 좌우 자목의 깊이 차이가 1을 넘지 않는다면 그것은 균형 두 갈래 나무이다.
검지 offer 55-II 문제, Leetcode 110 문제:
두 갈래 나무의 뿌리 노드를 입력하여 이 나무가 균형 잡힌 두 갈래 나무인지 판단한다.
균형 이차수의 개념은 명확하게 말한다. 임의의 한 노드의 좌우 나무의 깊이차가 1을 초과해서는 안 된다. 그러면 각 나무의 좌우 나무의 깊이를 구하고 차이를 구하면 판단할 수 있다.

public boolean isBalanced(TreeNode root){
    if(root==null) return true;
    // ， 
    return isBalanced(root.left)&&isBalanced(root.right)&&(Math.abs(maxDepth(root.left)-maxDepth(root.right))<2);
}

위의 코드 계산은 모든 노드가 시작되는 두 갈래 나무가 그의 모든 하위 나무가 균형 두 갈래 나무인지 아닌지를 판단하고 대량의 중복 계산을 한다. 그러면 어떻게 이런 중복 계산을 줄일 수 있을까?
답은 잎결점부터 계산하고 모든 잎결점을 뿌리로 판단하는 자수, 균형수라면 그의 나무 높이, 그렇지 않으면 -1을 되돌린 다음에 그의 아버지 노드가 뿌리인 자수, 되돌아오는 나무 높이를 사용하여 계산한다.

    public boolean isBalanced2(TreeNode root){
        return recur(root)!=-1;
    }

    public int recur(TreeNode root){
        if (root==null) return 0;
        int left=recur(root.left);
        if(left==-1) return -1;
        int right=recur(root.right);
        if(right==-1) return -1;
        return Math.abs(left-right)>1?-1:Math.max(left,right)+1;
    }

두 갈래 나무의 서브 구조

검지offer 26번:
두 그루의 두 갈래 나무 A와 B를 입력하여 B가 A의 자 구조인지 아닌지를 판단한다.(빈 트리는 임의의 트리의 하위 구조가 아님을 약속함), B는 A의 하위 구조입니다. 즉, A에 B와 같은 구조와 노드 값이 나타납니다.
예:

  A:

     3
    / \
   4   5
  / \
 1   2
  B：
   4 
  /
 1

B는 A의 하위 트리와 같은 구조와 노드 값을 가지고 있기 때문에true를 되돌려줍니다.
이 문제는 내가 첫 번째로 반응한 것이다. A수종의 각 노드를 A의 어떤 나무의 뿌리 노드와 B로 비교해야 한다.그래서 나는 전체 트리에서 얻은 요소를 대기열이나 창고나 목록으로 저장해서 다시 판단해야 한다고 생각한다.하지만 나는 이미 한 번 즐거움을 누렸다. 누비면서 현재 노드를 누비면 현재 노드를 뿌리로 하는 자수에 대해 판단하는 것이 좋지 않겠는가?

public boolean isSubStructure(TreeNode A, TreeNode B){
    if(A==null || B==null) return false;
    return help(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
}

// A B 
// 
public boolean help(TreeNode A, TreeNode B){
    if(B==null) reurn false;
    if(A==null || A.val!=B.val) return false;
    return help(A.left,B.left)&&help(A.right,B.right);
}

두 갈래 나무의 재건

두 갈래 나무의 재건, 음...생각만 해도 쉬워요. 하기는 쉬워요...
검지offer 7번, Leetcode 105번:
두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.
예:

  preorder = [3,9,20,15,7]
  inorder = [9,3,15,20,7]

 

    3
   / \
  9  20
    /  \
   15   7

뭐랄까, 방금 이 제목을 보자마자 어리둥절한 표정을 지으며 마치 대학에서 배운 것 같지만, 응, 응, 끔찍하게 배웠어...

우선: 두 갈래 나무는 앞의 순서, 중간 순서든 뒤의 순서든 두루 돌아다니며 얻은 원소의 개수는 반드시 같다

그 다음: 앞의 첫 번째 노드는 반드시 전체 나무의 뿌리

셋째: 중서 역행 중 뿌리 노드 앞에 있는 것은 왼쪽 나무의 노드, 뒤에 있는 것은 오른쪽 나무의 노드

넷째: 만약에 뿌리 노드에 왼쪽 나무가 존재한다면 앞의 순서 반복에서 뿌리 노드 뒤에 있는 것은 반드시 왼쪽 나무의 값이다. 수량은 중간 순서 반복에서 왼쪽 나무의 개수와 같다

마지막으로 중복원소가 없다는 보증이 있습니다. 우리가 중차적으로 루트를 찾을 때 유일한 것입니다.

이로써 중서가 편리한 수조를 세 부분, 뿌리 노드, 왼쪽 나무와 오른쪽 나무로 나눌 수 있으며 왼쪽 나무에 대해 그들은 또 하나의 완성된 나무 구조로 상기 방법을 반복하면 된다.
무슨 뜻이죠?위의 제목에 대해:

  preorder = [3,9,20,15,7]
  inorder = [9,3,15,20,7]

 3 
 3   [9], [3], [15,20,7]
        3
       / \
      9  [15,20,7]

 [15,20,7] [20,15,7]
 

    3
   / \
  9  20
    /  \
   15   7

위 코드:

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder==null||preorder.size()==0) return null;
    int len=preorder.size();
    Map indexMap=new HashMap<>();
    for(int i=0;i indexMap){
    if(preStart>preend) return null;
    int rootVal=preorder[preStart];
    TreeNode root =new TreeNode(rootVal);
    int rootIndex=indexMap.get(rootVal);
    int leftNodes=rootIndex-instart;
    int rigthNodes=inEnd-rootIndex;
    root.left=buildTree(preorder,preStrat+1,preStrat+leftNodes,
                        inorder,inStart,rootIndex-1,
                        indexMap);
    root.right=buildTree(preorder,preEnd-rightNodes+1,preEnd,
                         inorder,rootIndex+1,inEnd,
                         indexMap);
    return root;
    
}

총결산

나무의 각종 조작 분치 사상은 매우 기묘한 사상이다. 나무 전체를 판단하려면 먼저 좌우 나무를 판단하고 순서대로 귀속시키며 귀속 퇴출의 경계 조건에 주의해야 한다.

참고 자료

leetcode 대응 문제 번호 및 해석