package src.leetcode;

import src.common.node.TreeNode;

import src.utils.GeneralUtils;

import src.utils.PrintTreeUtils;

import java.util.ArrayList;

import java.util.Deque;

import java.util.LinkedList;

import java.util.List;

class Solution {

public List<String> generateParenthesis(int n) {

List<String> list = new ArrayList<String>();

generate(0, 0, n,"",list);

return list;

}

private void generate(int left, int right, int total, String s,List<String> list){

if( left == total && right == total){

list.add(s);

return;

}

if( left < total) generate(left + 1, right, total, s + "(",list);

if( left > right) generate(left, right + 1, total, s + ")",list);

}

public boolean isValidBST(TreeNode root) {

Deque<TreeNode> stack = new LinkedList<TreeNode>();

double inorder = -Double.MAX_VALUE;

while (!stack.isEmpty() || root != null) {

while (root != null) {

stack.push(root);

root = root.left;

}

root = stack.pop();

// 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树

if (root.val <= inorder) {

return false;

}

inorder = root.val;

root = root.right;

}

return true;

}

public static void main(String[] args) {

TreeNode treeNode = GeneralUtils.constructNormalBinaryTree(new Integer[]{5,4,6,null,null,3,7});

PrintTreeUtils.printTreeNode(treeNode);

new Solution().isValidBST(treeNode);

}

}