[LeetCode Medium] BST - Validate Binary Search Tree !!

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    List<Integer> list = new ArrayList<Integer>();
    
    public boolean isValidBST(TreeNode root) {
        inorder(root);
        for (int i = 0; i < list.size() - 1; i++) {
			if(list.get(i) >= list.get(i+1))
				return false;
		}
        return true;
    }
    
    public void inorder(TreeNode node) {
		if(node != null) {
			inorder(node.left);			
			list.add(node.val);
			inorder(node.right);
		}
	}
    
}

 

- 처음에는 DFS로 하려고 했는데, val을 비교하는 과정이 복잡해져서, inorder 순회해서 list에 넣었음

- inorder로 순회하며 list에 val을 넣으면 valid한 B-Tree라면 list에 val이 오름차순으로 들어있을 것임 => 오름차순인지 검사해서 맞으면 true, 아니면 false

 

- inorder : 왼쪽 > 루트 > 오른쪽

- preorder : 루트 > 왼쪽 > 오른쪽

- postorder : 왼쪽 > 오른쪽 > 루트

 

B-Tree 순회방법 참고 => https://youtu.be/QN1rZYX6QaA