leetCode 문제 풀이 보고서 5 문제 (3)

제목 1:
Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example: Given binary tree  {3,9,20,#,#,15,7} ,

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

confused what  "{1,#,2,3}"  means? > read more on how binary tree is serialized on OJ.
분석: 층 차 를 옮 겨 다 니 는 변형 이 군요. 큰 변화 가 없습니다. 코드 를 보고 이해 하 세 요!

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null)
            return result;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int k = 1;
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        
        while (!queue.isEmpty()){
            list.clear();
            while (!queue.isEmpty()){
                list.add(queue.remove());
            }
            ArrayList<Integer> arrays = new ArrayList<Integer>();
            
            for(int i=0; i<list.size(); ++i){
                TreeNode node = list.get(i);
                if (k % 2 == 1){
                    arrays.add(list.get(i).val);
                }else{
                    arrays.add(list.get(list.size()-1-i).val);
                }
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            k++;
            result.add(arrays);
        }
        return result;
    }
}

제목 2:
Convert Sorted Array to Binary Search Tree
 Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
제목: array 배열 을 하나 드 리 겠 습 니 다. 이 배열 로 구 성 될 수 있 는 균형 적 인 이 진 트 리 를 구 하 겠 습 니 다. 분명 한 재 귀 문제 입 니 다. 분 치 된 사상 으로 중간의 결점 을 근결 점 으로 하고 계속 재 귀 하면 됩 니 다!!
AC 코드:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num.length == 0){
            return null;
        }
        return buildBST(num, 0, num.length-1);
    }
    /*
            
    */
    public TreeNode buildBST(int[] num, int left, int right){
        /* left > right    ，           ，  null*/
        if (left > right){
            return null;
        }
        /*    ，       */
        int middle = (right + left) / 2;
        TreeNode root = new TreeNode(num[middle]);
        /*      */
        root.left = buildBST(num, left, middle-1);
        root.right = buildBST(num, middle+1, right);
        return root;
    }
}

비슷 한 제목:
Convert Sorted List to Binary Search Tree
 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
제목: 위 와 마찬가지 로 배열 이 링크 로 바 뀌 었 을 뿐!!과감하게 링크 중간 에 있 는 점 을 빨리 구 하 는 방법 을 알 아야 돼 요.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null){
            return null;
        }
        return buildBST(head, null);
    }
    
    public TreeNode buildBST(ListNode left, ListNode right){
        if (right == null && left == null){
            return null;
        }
        if (right != null && right.next == left){
            return null;
        }
        /*              Begin*/
        ListNode preLeft = new ListNode(0);
        preLeft.next = left;
        ListNode tempNode = left;
        ListNode preMiddleNode = preLeft;
        /*            */
        while (tempNode != right && tempNode.next != right){
            preMiddleNode = preMiddleNode.next;
            tempNode = tempNode.next.next;
        }
        /*              End*/
        
        /*   ！*/
        ListNode middleNode = preMiddleNode.next;
        TreeNode root = new TreeNode(middleNode.val);
        root.left = buildBST(left, preMiddleNode);
        root.right = buildBST(preMiddleNode.next.next, right);
        return root;
    }
}

제목 3:
주변 지역 (심층 검색 고찰)
 
Given a 2D board containing  'X'  and  'O' , capture all regions surrounded by  'X' .
A region is captured by flipping all  'O' s into  'X' s in that surrounded region.
For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

분석: x (또는 X) 와 o (또는 O) 가 포 함 된 배열 을 드 립 니 다. o (또는 O) 가 x (또는 X) 에 둘러싸 인 상황 을 변환 하 라 고 요구 합 니 다. o -> x  그리고 O -> X
이 문 제 는 사실 전형 적 인 광범 위 한 검색 이 죠.
문제 풀이 방법: 모든 경계 o (또는 O), 우 리 는 그것 이 포위 되 지 않 는 다 고 생각 합 니 다. 그러면 우 리 는 경계 에서 시작 하면 됩 니 다. 우 리 는 2 차원 배열 flags 로 모든 위치 에 어떤 자모 가 나 와 야 하 는 지 확인 합 니 다. 예 를 들 어 flags [row] [col] = 0 개의 row 줄 col 열 에 나타 난 자 모 는 x (또는 X) 입 니 다. flags [row] [col] = 1 개의 row 행 col 열 에 나타 난 알파벳 은 o (또는 O) 입 니 다. 
경계 에 있 는 모든 o (또는 O) 를 queue 에 추가 한 다음 에 전형 적 인 BFS 입 니 다. 줄 을 돌아 서 입대 하고 표 시 를 해 야 합 니 다. 대열 에서 나 가면 이 위치 가 X 에 둘러싸 이지 않 았 음 을 증명 합 니 다. 그러면 이 위 치 를 플래그 [row] [col] = 1 로 표시 합 니 다.
그 다음 에 flags 라 는 2 차원 배열 만 순환 하면 됩 니 다.
AC 코드:

public class Solution {
    private int[][] flags;//           
	private int rowLength;//  
	private int colLength;//  
	
	/*     queue        */
	class Node{
		int i;
		int j;
		public Node(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}
	
	public void solve(char[][] board){
	    /*   */
		rowLength = board.length;
		if (rowLength == 0 || board[0].length == 0)
			return ;
		colLength = board[0].length;
		
		/*   flags, queue,    board[][]       o(  O)     queue*/
		flags = new int[rowLength][colLength];
		Queue<Node> queue = new LinkedList<Node>();
		for (int i=0; i<rowLength; ++i){
			for (int j=0; j<colLength; ++j){
				if (i == 0 || i == rowLength - 1){
					if (board[i][j] == 'o' || board[i][j] == 'O'){
						queue.add(new Node(i,j));
					}
				}else{
					if (j == 0 || j == colLength - 1){
						if (board[i][j] == 'o' || board[i][j] == 'O'){
							queue.add(new Node(i,j));
						}
					}
				}
				
			}
		}
		/*BFS*/
		while (!queue.isEmpty()){
			Node node = queue.remove();
			int row = node.i;
			int col = node.j;
			flags[row][col] = 1;
			//left
			if (col-1 >= 0 && (board[row][col-1] == 'o' || board[row][col-1] == 'O' )&& flags[row][col-1] == 0){
				queue.add(new Node(row,col-1));
			}
			//right
			if (col+1 < colLength && (board[row][col+1] == 'o' || board[row][col+1] == 'O') && flags[row][col+1] == 0){
				queue.add(new Node(row,col+1));
			}
			//up
			if (row-1 >= 0 && (board[row-1][col] == 'o' || board[row-1][col] == 'O')&& flags[row-1][col] == 0){
				queue.add(new Node(row-1,col));
			}
			//down
			if (row+1 < rowLength && (board[row+1][col] == 'o' || board[row+1][col] == 'O')&& flags[row+1][col] == 0){
				queue.add(new Node(row+1,col));
			}
		}
		/*    board[][]*/
		for (int i=0; i<rowLength; ++i){
			for (int j=0; j<colLength; ++j){
				if (flags[i][j] == 0){
					if (board[i][j] == 'o'){
						board[i][j] = 'x';
					}else if (board[i][j] == 'O'){
						board[i][j] = 'X';
					}
				}
				//System.out.print(board[i][j] + " ");
			}
			//System.out.println("");
		}
	}
}

제목 4:
Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. 분석: 고찰 한 것 은 바로 균형 이 진 트 리 개념 에 대한 이해 와 이 진 트 리 의 깊이 를 구 하 는 방법 에 대한 파악 이다.
한 그루 의 이 진 트 리 가 균형 적 인 조건 을 만족 시 키 면 그 자신 을 포함 하고 그 어떠한 키 트 리 와 의 좌우 서브 트 리 의 깊이 차 이 는 반드시 2 보다 작 아야 한다. 그러면 문 제 는 재 귀 적 인 것 으로 바 뀌 고 계속 재 귀 되 어야 한다. 조건 을 만족 시 키 지 않 으 면 전체적인 표지 flag 를 false 로 설치한다.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private boolean flag = true;

	public boolean isBalanced(TreeNode root) {
		calDeepthByTree(root);
		return flag;
	}

	public int calDeepthByTree(TreeNode root) {
		if (root == null)
			return 0;
		if (root.left == null && root.right == null)
			return 1;

		int deepLeft = 0;
		int deepRight = 0;
		deepLeft = calDeepthByTree(root.left) + 1;
		deepRight = calDeepthByTree(root.right) + 1;
		if (Math.abs(deepRight - deepLeft) >= 2) {
			flag = false;
		}
		return deepRight > deepLeft ? deepRight : deepLeft;
	}
}

제목 5:
Minimum Depth of Binary Tree
 
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
분석: 우리 에 게 이 진 트 리 를 주 고 뿌리 결산 점 에서 잎 결산 점 까지 의 가장 짧 은 경 로 를 요구 합 니 다 (여전히 재 귀 합 니 다!)
간단 합 니 다. 코드 를 직접 보 세 요.
AC 코드:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        /*      */
        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return 1;
        
        int leftdepth = minDepth(root.left);
        int rightdepth = minDepth(root.right);
        
        /*            null   ，            ，            */
        if (leftdepth == 0){
            return rightdepth+1;
        }
        if (rightdepth == 0){
            return leftdepth+1;
        }
        
        /*            */
        return leftdepth > rightdepth ? rightdepth + 1 : leftdepth + 1;
    }
}