공간 대가 대체 시간 대가 - LeetCode105 - 전차와 중차 역행 서열 구조 두 갈래 나무

2260 단어
제목
 。
 :
 。
 , 
  preorder = [3,9,20,15,7]
  inorder = [9,3,15,20,7]
 :
    3
   / \
  9  20
    /  \
   15   7

생각
첫 번째 요소는 트리의 루트 노드입니다.중서는 이 뿌리 노드에 의해 두 부분으로 나뉘는데 왼쪽 부분은 뿌리 노드 왼쪽에 있고 오른쪽 부분은 뿌리 노드 오른쪽에 있다.각각 왼쪽 부분과 오른쪽 부분에서 뿌리 결점을 찾습니다.이렇게 차례로 돌아가다.귀속 매개 변수: 루트 노드, 루트 결점에 의해 분리된 그룹.귀속 방법: 뿌리 노드에 따라 수조를 분리하고 분리 부분의 뿌리 노드를 각각 찾아서 귀속한다.
코드
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public static  Map map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0){
            return null;
        }
        // map , , for 
        map = new HashMap();
        for(int i=0;i

주의하다
처음 쓴 코드는 주석이 떨어진 코드로 시간을 초과합니다.시간 초과 문제를 해결하기 위해 맵 형식을 도입하여 for 순환에서 얻은 값을 맵에 저장하고 공간 대가로 시간 대가를 줄인다.
생각 2
외부 순환은 선서수 그룹을 두루 훑어보고 첫 번째 요소는 루트 노드입니다.두 번째 원소와 첫 번째 원소가 중서수 그룹의 위치를 비교하고 위치가 뿌리 결점의 왼쪽인지 오른쪽인지 판단한다.세 번째 원소와 첫 번째 원소가 중서수 그룹의 위치를 비교한다. 만약에 왼쪽에 있으면 첫 번째 원소의 왼쪽이 비어 있는지 판단하고 만약에 비어 있으면 세 번째 원소를 여기에 놓고 만약 비어 있지 않으면 세 번째 원소는 다시 첫 번째 원소의 왼쪽에 있는 원소와 두 번째 라운드를 비교한다.이렇게 유추하다.
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0){
            return null;
        }
        TreeNode[] treenodes=new TreeNode[preorder.length];
        for(int i=0;i

주의하다
시간을 초과하면 맵 형식을 이용하여 for순환을 줄이고 공간 대가로 시간 대가를 줄일 수 있습니다.

좋은 웹페이지 즐겨찾기