树&二叉树&二叉搜索树&图

• 树（Tree）

  
  image.png

• Binary Tree

• 二叉搜索树（Binary Search Tree）

  
  image.png
  

  为什么要发明二叉树？
  是为了更好的查找树种的元素。让搜索少了一半的时间

• 图（Graph）

  
  image.png

• Linked List就是特殊化的Tree

• Tree就是特殊化的Graph

• 验证二叉搜索树
  https://leetcode-cn.com/problems/validate-binary-search-tree/submissions/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        // 利用二叉搜索树的中序遍历来判断
        List<Integer> list = new ArrayList<>();
        inOrder(root, list);
        for(int i = 1; i < list.size(); i++) {
            if (list.get(i - 1) >= list.get(i)) {
                return false;
            }
        }
        return true;
    }
    
    // 依次把树中的数据添加到数组
    private void inOrder(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        inOrder(node.left, list);
        list.add(node.val);
        inOrder(node.right, list);
    }
}