CODE 35: Validate Binary Search Tree

1474 단어 leetcode
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.

  • confused what  "{1,#,2,3}"  means? > read more on how binary tree is serialized on OJ.
    OJ's Binary Tree Serialization:
    The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
    Here's an example:
       1
      / \
     2   3
        /
       4
        \
         5
    
    The above binary tree is serialized as  "{1,2,3,#,#,4,#,#,5}" .
    	public boolean isValidBST(TreeNode root) {
    		// Start typing your Java solution below
    		// DO NOT write main() function
    		if (null == root) {
    			return true;
    		}
    		Stack stack = new Stack();
    		TreeNode pre = new TreeNode(Integer.MIN_VALUE);
    		TreeNode now = root;
    		while (!stack.isEmpty() || null != now) {
    			if (null == now) {
    				now = stack.pop();
    				if (pre.val >= now.val) {
    					return false;
    				}
    				pre = now;
    				now = now.right;
    			} else {
    				stack.push(now);
    				now = now.left;
    			}
    		}
    		return true;
    	}

    좋은 웹페이지 즐겨찾기