두 갈래 나무의 앞 순서, 중간 순서, 뒤 순서, 깊이 우선 검색, 폭 우선 검색

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

선행 순서(Pre-order)

public void preorder(TreeNode root) {
	if(root != null){
		System.out.println(root.val);
		preorder(root.left);
		preorder(root.right);
	}
}

중간 순서 반복(In-order)

public void inorder(TreeNode root) {
	if(root != null){
		inorder(root.left);
		System.out.println(root.val);
		inorder(root.right);
	}
}

후행 반복(Post-order)

public void postorder(TreeNode root) {
	if(root != null){
		postorder(root.left);
		postorder(root.right);
		System.out.println(root.val);
	}
}

광범위한 우선 순위 검색(BFS)


광범위한 우선 검색(Breadth-First-Search)은 루트 노드에서 시작하여 층층이 접근하여 직관적인 생각에 비교적 부합된다.대기열의 선진적인 선출 특성을 사용하여 특정한 층 노드를 방문한 후 이 층 노드를 대열에서 내보내고 하위 노드를 순서대로 대열에 넣는다.이렇게 순환하다.
public void BFS(TreeNode root){
	if (root == null) {  
		return;  
    }  
    LinkedList<TreeNode> queue = new LinkedList<>();  
    queue.offer(root);  
    while (!queue.isEmpty()) {  
    	TreeNode node = queue.poll();  
	    System.out.println(node.val);  
    	if (node.left != null)
	    	queue.offer(node.left);  
        if (node.right != null)
        	queue.offer(node.right); 
    }  
}

깊이 우선 순위 검색(DFS)


깊이 우선 검색(Depth-First-Search)은 컴퓨터의 처리 방식에 따라 스택 구조를 사용합니다.
public void BFS(TreeNode root){
	if (root == null) {  
		return;  
    }  
    LinkedList<TreeNode> stack = new LinkedList<>();  
    stack.push(root);
    while(!stack.isEmpty()){
    	TreeNode node = stack.pop();
    	system.out.println(node.val);
    	if(node.right!=null)
    		stack.push(node.right);
    	if(node.left!=null)
    		stack.push(node.left);
    }  
}

참조 연결:https://leetcode.com/problems/validate-binary-search-tree/solution/

좋은 웹페이지 즐겨찾기