검지 Offer 07.두 갈래 나무를 재건하다

1. 제목


두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복preorder =[3,9,20,15,7] 중 순서 반복inorder =[9,3,15,20,7] 출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.

2. 해법


2.1 위에서 아래로 귀속


생각

  • 위에서 아래로 귀속적으로 두 갈래 나무를 구성하고 매번 하나의 노드를 구성한다
  • 선차적 역행 특징에 따라 구간의 가장 왼쪽 원소는 뿌리 노드이다
  • 중서 역행 특징에 따라 뿌리 노드의 왼쪽은 왼쪽 나무, 오른쪽은 오른쪽 나무이다

  • 핵심 단계:
  • 먼저 뿌리 노드를 구성한다
  • 선서, 중서수 그룹의 왼쪽 트리 구간을 사용하고 귀속적으로 왼쪽 트리를 구성한다
  • 선서, 중서수 그룹의 오른쪽 트리 구간을 사용하여 귀속적으로 오른쪽 트리를 구성한다
  • 마지막으로 루트 노드로 돌아갑니다

  • 코드

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            // preL,preR,inL,inR 
            return buildTreeCore(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
        }
    
        public TreeNode buildTreeCore(int[] preorder, int preL, int preR, int[] inorder, int inL, int inR){
            //  
            if(preL>preR||inL>inR){
                return null;
            }
            //  
            TreeNode root = new TreeNode(preorder[preL]);
            //  , , 
            for(int i=inL; i<=inR; i++){
                if(inorder[i]==preorder[preL]){
                    
                    root.left = buildTreeCore(preorder, preL+1, preL+i-inL, inorder, inL, i-1);
                    root.right = buildTreeCore(preorder, preL+i-inL+1, preR, inorder, i+1, inR);
                    break;
                }
            }
            return root;
        }
    

    좋은 웹페이지 즐겨찾기