Leetcode가 알고 있는 전차순(후차순) 전차순과 중차순 전차순 구축 트리

2671 단어 나무.
우리는 중서가 왼쪽 나무->뿌리 노드->오른쪽 나무라는 것을 안다.따라서 우리는 중서를 통해 좌우 나무의 원소 개수를 정할 수 있다.
그리고 앞의 순서(뒤의 순서)를 통해 우리는 뿌리 노드의 위치를 확정한 다음에 뿌리 노드가 중간에서 두루 다니는 위치를 찾아 좌우 트리를 확정할 수 있다.
그리고 좌우 트리로 돌아가 두 갈래 트리를 구축한다.
앞 및 가운데 순서:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
           if(preorder==null&&inorder==null)
               return null;
           return rebuild (preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }
    private TreeNode rebuild(int[] preorder, int[] inorder,int preleft,int preright,int inleft,int inright)
    {
           if(preleft>preright||inleft>inright)
               return null;
           TreeNode t=new TreeNode(preorder[preleft]);
           t.left=t.right=null;
           int loc=0;
           // 
           for (int i=inleft;i<=inright;i++)
               if(inorder[i]==preorder[preleft])
               {
                   loc=i;
                   break;
               }
          //preleft+1 ,preleft+loc-inleft 
           t.left=rebuild (preorder,inorder,preleft+1,preleft+loc-inleft,inleft,loc-1);
         //preleft+loc-inleft+1 ,preright 
           t.right=rebuild (preorder,inorder,preleft+loc-inleft+1,preright,loc+1,inright);
           return t;
    }
}

뒷 순서와 중간 순서:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
         if(inorder==null&&postorder==null)
             return null;
         return rebuild (inorder,postorder,0,postorder.length-1,0,inorder.length-1);
    }
    private TreeNode rebuild(int[] in, int[] post,int postleft,int postright,int inleft,int inright)
    {
        if(postleft>postright||inleft>inright)
            return null;
        int loc=-1;
        TreeNode t=new TreeNode(post[postright]);
        t.left=t.right=null;
        for (int i=inleft;i<=inright;i++)
            if(in[i]==post[postright])
            {
                loc=i;
                break;
            }
        //postright-inright+loc-1 ,posleft 
        t.left=rebuild (in,post,postleft,postright-inright+loc-1,inleft,loc-1);
        //postright-1 ,postright-inright+loc 
        t.right=rebuild(in,post,postright-inright+loc,postright-1,loc+1,inright);
        return t;
        
    }
}

좋은 웹페이지 즐겨찾기