leetcode_Validate Binary Search Tree

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.

解題思路

題目的意思就是判斷一個給定的二叉樹是不是二叉搜索樹，二叉搜索樹要求對每個節點，其左兒子節點數值小於父節點數值，右兒子節點數值大於父節點數值，並且左側子樹上的數值都小於父節點，右側子樹所有數值都大於父節點，也就是按此規則嚴格有序的，實際上我們中序遍歷便可得到從小到大排序的元素序列，這裡我們通過對中序遍歷得到的List進行判斷是否有來決定此二叉樹是否為二叉搜索樹。(這裡涉及二叉搜索樹和線序遍歷有序兩個概念的充分必要性，可以自行證明)

詳細代碼

二叉樹的前中後序遍歷通過遞歸可以很簡單地寫出代碼，leetcode上也有要求迭代實現的，後續也會講解。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
        //Validate Binary Search Tree
    //Given a binary tree, determine if it is a valid binary search tree (BST).
    public boolean isValidBST(TreeNode root) 
    {


        ArrayList resultList = inorderTraversal(root);
        if(resultList.size()>=2)
        {
            for (int i = 0; i < resultList.size()-1; i++)
            {
                if (resultList.get(i)>=resultList.get(i+1))
                {
                    return false;
                }
            }
        }
            return true;

    }

    //recursively do it  middle order
  public ArrayList inorderTraversal(TreeNode root) 
  {
    ArrayList results = new ArrayList();
    if(root == null)
    {
        return results;
    }
    else 
    {   
        results.addAll(inorderTraversal(root.left));//traverse left 
        results.add(root.val);//traverse the parent node
        results.addAll(inorderTraversal(root.right));//traverse right
        return results;
    }
  }
}

總結

這裡需要理解二叉搜索樹的概念，類似地如何建立二叉搜索樹(BST)，二叉搜索樹地插入刪除操作也是需要研究的，當然有興趣滴可以去研究下，平衡二叉樹(AVL),紅黑樹(RBT),字典樹(TRIE)等。