[LeetCode] Validate Binary Search Tree

문제

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

 

Example 1:

2 / \ 1 3 Input: [2,1,3] Output: true

Example 2:

5 / \ 1 4   / \   3 6 Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.

 

Approach

Binary Search Tree의 정의에 따르면 왼쪽 subtree의 모든 값은 현 node의 값 보다 작아야 하고,

오른쪽 subtree의 모든 값은 현 node의 값 보다 커야한다.

그러므로 inorder traversal로 트리를 탐색하며 탐색할 경우 값이 정렬 되어있으면(그리고 중복되는 값이 없으면) valid한 트리이다.

Inorder traversal은 stack으로 구현하였다.

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_ValidateBinarySearchTree.cpp

chi3236/algorithm