初涉深度优先搜索--Java学习笔记（二）

时间：2021-09-25 03:41:44

版权声明：

本文由Faye_Zuo发布于http://www.cnblogs.com/zuofeiyi/, 本文可以被全部的转载或者部分使用，但请注明出处.

上周学习了数组和链表，有点基础了解以后，这周初步探索了一下深度优先搜索。对于文科生的我来说，这个名词听起来有点可怕。于是我通过leetcode上的一个难度为medium的题目来逐渐认识这个概念的。这道题目是Validate Binary Search Tree（题号为98）。下面我将通过这道题作为引子，整理一下上周学习到的东西。

一、树

这道题目是让我们判断这棵树是否为有效二叉查找树。但是我连树是什么都是一脸茫然。后来通过学习youtube上的视频，对他有逐步了解。树的概念容易理解，现在主要看看它的存储结构（其实我也不知道了解到存储结构有什么用）

树的存储结构如下：
初涉深度优先搜索--Java学习笔记（二）
（1）双亲表示法
以一段连续空间来存储树的结点，在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。这样，每个结点除了知道自己是谁以外，还知道自己双亲的位置。
初涉深度优先搜索--Java学习笔记（二）
（2）孩子表示法：用多重链表来表示
（3）双亲孩子表示法：上述两种的结合
初涉深度优先搜索--Java学习笔记（二）

二、二叉树（Binary Tree)

有了对树的认识以后，二叉树的基本概念就更加容易理解了。

1.概念：每个节点最多有两个节点的结构树，通常子树被称为左子树和右子树。
 
2.二叉树的建立（非常重要）
 
public static void main(String[] args) {

    /* Making a tree like :

               0

             /  \

            1    2

          /

         3

     */

    TreeNode root = new TreeNode(0);

    root.left = new TreeNode(1);

    root.right = new TreeNode(2);

    root.left.left = new TreeNode(3);
3.二叉树的遍历
 private static class TreeNode {
    public TreeNode(int x) {    //红色标记部分不是成员函数，是构造函数，主要用来初始化的。所以也不需要有返回值类型。
      this.x = x;
    }
 
    public int x;
    public TreeNode left;//left和right就是变量
    public TreeNode right;
  }
 
  /* pre-order, 先序遍历 */
  private static void traverseTreePreOrder(TreeNode node) {
    if (node != null) {
      System.out.println(node.x);
      traverseTreePreOrder(node.left);
      traverseTreePreOrder(node.right);
    }
  }
 
  /* in-order, 中序遍历 */
  private static void traverseTreeInOrder(TreeNode node) {
    if (node != null) {
      traverseTreeInOrder(node.left);
      System.out.println(node.x);
      traverseTreeInOrder(node.right);
    }
  }
 
  /* post-order, 后序遍历 */
  private static void traverseTreePostOrder(TreeNode node) {
    if (node != null) {
      traverseTreePostOrder(node.left);
      traverseTreePostOrder(node.right);
      System.out.println(node.x);
    }
  } 
 
三、然后我就可以开始看看这道leetcode上的题目了
Validate Binary Search Tree（98）
Given a binary tree, determine if it is a valid binary search tree(BST).
Assume a BST is defined as follows:
（1）The left subtree of a node contains only nodes with keys less than the node’s key.
（2）The right subtree of a node contains only nodes with keys greater than the node’s key.
（3）Both the left and right subtrees must also be binary search trees. 
初涉深度优先搜索--Java学习笔记（二）
 
完全不会做啊，于是只有看答案，发现这道题主要要用到递归，思路如下：
 
1.所有的在左边的值必然小于root,所有在右边的值必然大于root。
2.我们要看的是每个节点是不是都满足BST。
3.我们要将这个上限和下限代入递归中。 
 
完整解答的程序：
public class BinarySearchTree {

public static void main(String[] args) {
    TreeNode root=new TreeNode(6);
    root.left=new TreeNode(1);
    root.right=new TreeNode(7);
    root.left.left=new TreeNode(4);
   

    Solution A=new Solution();
    System.out.println(A.isValidBST(root));//为什么new了新对象，还需要将下面的方法改为静态？原因就是看下面的方法是不                        
                                                            //是访问到了对象中特有数据。如果访问到了，加static。
 
  }
  public static class TreeNode{
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x){
      val=x;
    }
  }
 
  public static class Solution{
    public  boolean isValidBST(TreeNode root){
      return isValidBST(root,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
    }
   
    public boolean isValidBST(TreeNode p,double min, double max){
      if(p==null)
        return true;
     
      if(p.val<=min||p.val>=max)
        return false;
 
      return isValidBST(p.left,min,p.val)&&isValidBST(p.right,p.val,max);
    }
   
   
  }
  }
 
 
在以上的程序中，我发现我有好多知识点都需要再学习，再补充。整理如下：
1.一些固定需要记住的class
Double.NEGATIVE_INFINITY 表示负数无穷小
Double.POSITIVE_INFINITY 表示正数无穷大
 
2.需要死记的一个算法（写得真的太好了）
public  boolean isValidBST(TreeNode root){
      return isValidBST(root,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
    }
   
    public boolean isValidBST(TreeNode p,double min, double max){
      if(p==null)
        return true;
     
      if(p.val<=min||p.val>=max)
        return false;
 
      return isValidBST(p.left,min,p.val)&&isValidBST(p.right,p.val,max);
    }
 
 
3.java中关于静态知识点的讲解
（1）成员变量又叫实例变量，但是静态变量又叫类变量，它是类能直接访问的变量。
（2）成员变量和静态变量的区别：
生命周期：成员变量随着对象的创建而存在，随着对象的回收而释放。静态变量随着类的存在而存在，随着类的消失而消失。
调用方式：成员变量只能被对象调用。静态对象可以被类名调用，也可以被对象调用。
数据存储位置不同：成员变量存储在堆内存的对象中，静态变量存储在方法区中。
（3）static在使用过程中应该注意的细节：
   a.静态方法只能访问静态成员。注意一个常见的报错：无法从静态方法中调用非静态。原因是静态变量会先加载，加载的时候非静态变量中还没有对象。
   b.静态方法中不可以使用this或者super关键字。
   c.主函数一定是静态的。
 (4) 什么时候使用static关键字
静态变量:当对象中所具备的成员变量的值是相同的，这时成员可以被静态修饰。
静态函数:关注一点! 该函数的功能是否访问到对象中的特有数据（特有数据：对象的值）。
 
 4. 递归
(1).递归的最基本思想：自己调用自己
(2).递归必须要有一个出口，即告诉别人什么时候可以不用调用了。否则这个函数会进入一个死循环，直到栈溢出。说白了就是一个if else
(3).递归的特点：耗时间、耗空间（一层一层的调用，再一层一层的返回） 
 
5. 补充面向对象的基本知识
(1)什么是方法：方法就是函数（method）
 
(2)方法的重载：
其实就是同一方法名下，通过参数的不同，可以实现函数的不同功能。
public void tell(int i,int j){}
public void tell(string k){} 
 
本周学习的东西就大致整理分享到这里，下周准备再多练习几道leetcode关于树的题目。希望可以对树这种数据结构有更加深入的理解！
加油！
 

相关文章