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,4,null,3,6]
Output: false
Explanation: The root node‘s value is 5 but its right child‘s value is 4.

思路

　　在看到这道题的时候，我想起了二叉搜索树的一个特性就是二叉搜索树的中序遍历是升序排序的。因此根据这个特性。我得出二叉搜索树的中序遍历序列，然后从头到尾进行判断他是否是有序的。如果其中哪一个数字大小关系不满足，则说明不是有效的二叉搜索树。时间复杂度为O(n)，空间复杂度为O(n)。
解决代码

 1 # DeFinition for a binary tree node.
 2 # class TreeNode(object):
 3 # def __init__(self,x):
 4 # self.val = x
 5 # self.left = None
 6 # self.right = None
 7 
 8 class Solution(object):  9     def isValidBST(self,root): 10         """
11  :type root: TreeNode 12  :rtype: bool 13         """
14         if not root: 15             return True 16         res = [] 17  self.validBFS(root,res) 18         for i in range(1,len(res)): # 从头到尾进行判断是否存在不满足排序的元素。 19             if res[i] <= res[i-1]: 20                 return False 21         return True 22         
23         
24     def validBFS(self,root,res): # 中序遍历函数，将遍历序列添加进去 25         if not root: 26             return
27  self.validBFS(root.left,res) 28  res.append(root.val) 29         self.validBFS(root.right,res)

非递归解决办法

 1 # DeFinition for a binary tree node.
 2 # class TreeNode(object):
 3 # def __init__(self,root): 10         """
11  :type root: TreeNode 12  :rtype: bool 13         """
14         if not root: 15             return True 16         res,stack = [],[] 17         
18         while stack or root: 19             if root: 20  stack.append(root) 21                 root = root.left 22             else: 23                 root = stack.pop() 24 if res and root.val <= res： # 每次添加前先判断   
return False 26  res.append(root.val) 27                 root = root.right 28         return True

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:

Input:
    2
   /   1   3
Output: true
Example 2:

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

如果对BST 中序遍历， 会产生有序数列。

/**
 * DeFinition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //BST inorder traverse will generate a ordered sequnence
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        
        List<Integer> list = new ArrayList<>();
        list.add(null);
        return helper(root,list);
    }
    
    public boolean helper(TreeNode node,List<Integer> list){
        if(node == null){
            return true;
        }
        boolean left = helper(node.left,list);
        
        if(list.get(list.size()-1) != null && node.val <= list.get(list.size()-1)){
            return false;
        }
        list.add(node.val);
        boolean right = helper(node.right,list);
        
        return left && right;
    }
}

题目描述：

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10,-3,5,9],一个可能的答案是：[0,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树：

      0
     /    -3   9
   /   /
 -10  5

解法：

/**
 * DeFinition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x),next(NULL) {}
 * };
 */
/**
 * DeFinition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(head == NULL){
            return NULL;
        }else if(head->next == NULL){
            return new TreeNode(head->val);
        }else{
            ListNode* node = new ListNode(0);
            node->next = head;
            ListNode* cur = node,* ltail = node;
            while(cur != NULL){
                
                cur = cur->next;
                if(cur == NULL){
                    break;
                }else{
                    cur = cur->next;
                }
                if(cur != NULL){
                    ltail = ltail->next;
                }
            }
            // cout<<ltail->val<<endl;
            TreeNode* root = new TreeNode(ltail->next->val);
            root->right = sortedListToBST(ltail->next->next);
            ltail->next = NULL;
            root->left = sortedListToBST(head);
            return root;
        }
    }
};

题目描述：

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

• 结点左子树中所含结点的值小于等于当前结点的值
• 结点右子树中所含结点的值大于等于当前结点的值
• 左子树和右子树都是二叉搜索树

示例：

给定 BST [1,null,2,2],

1
         2
    /
   2
返回[2].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

解法：

/**
 * DeFinition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 * };
 */

class Solution {
public:
    void inorder(TreeNode* root,TreeNode*& pre,int& curTimes,int& maxTimes,vector<int>& res){
        if (!root) return;
        inorder(root->left,pre,curTimes,maxTimes,res);
        if (pre)
            curTimes = (root->val == pre->val) ? curTimes + 1 : 1;
        if (curTimes == maxTimes)
            res.push_back(root->val);
        else if (curTimes > maxTimes){
            res.clear();
            res.push_back(root->val);
            maxTimes = curTimes;
        }
        pre = root;
        inorder(root->right,res);
    }
    
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        TreeNode* pre = NULL;
        int curTimes = 1,maxTimes = 0;
        inorder(root,res);
        return res;
    }
};