目录

• 题库
• 一、二叉树的三种遍历方式（递归思维）
• • 1.前序遍历
  • 2.中序遍历
  • 3.后序遍历
• 二、验证二叉搜索树
• • 1.递归解法
  • 2.中序遍历解法
• 总结

题库

一、二叉树的三种遍历方式（递归思维）

给你二叉树的根节点 root ，返回它节点值的 前序（中序，后序） 遍历。

1.前序遍历

原题
代码如下：

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> st = new ArrayList<Integer>();
        diGui(root,st);
        return st;
    }

    public static void diGui(TreeNode root,List<Integer> st) {
        if(root == null)
            return;
        st.add(root.val);
        diGui(root.left,st);
        diGui(root.right,st);
    }

2.中序遍历

原题
代码如下：

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> st = new ArrayList<Integer>();
        diGui(root,st);
        return st;
    }

    public static void diGui(TreeNode root,List<Integer> st) {
        if(root == null)
            return;
        diGui(root.left,st);
        st.add(root.val);
        diGui(root.right,st);

3.后序遍历

原题
代码如下：

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> st = new ArrayList<Integer>();
        diGui(root,st);
        return st;
    }

    public static void diGui(TreeNode root,List<Integer> st) {
        if(root == null)
            return;
        diGui(root.left,st);
        diGui(root.right,st);
        st.add(root.val);
    }

二、验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
原题

1.递归解法

该解法主要利用根结点大于左子结点，小于右子结点，设立一个原始的最大值和最小值，重复调用函数去判断左右两个子结点是否正确。
代码如下：

	public boolean isValidBST(TreeNode root) {
        return diGui(root,Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public static boolean diGui(TreeNode root,long lower,long upper) {
        if(root == null)
            return true;
        if(root.val <= lower || root.val >= upper)
            return false;
        return diGui(root.left,lower,root.val) && diGui(root.right,root.val,upper);
    }

2.中序遍历解法

二叉树的中序遍历的结果符合二叉搜索树的要求，即先访问的结点的值小于后访问的结点的值。
该代码参考他人。原本
代码如下：

long preNum = Long.MIN_VALUE;
	public boolean isValidBST(TreeNode root) {
		if(root == null)//已访问到叶子结点，一切正常，返回true
			return true;
		if(!isValidBST(root.left))//如果左子树正常，则不执行该if语句
			return false;
		if(root.val <= preNum)//判断当前根结点的值是否大于前一个结点的值（即左子结点的值）是否正常
			return false;
		preNum = root.val;
		return isValidBST(root.right);//到此处，左子树和根结点均正常，则结果看右子树是否正常
	}

总结