leetcode热题100训练计划

路径总和

题目

思路

没思路，试试递归。
先分类讨论

1. 算上本身结点，在递归里搜左右子树
2. 不算本身结点，在左子树或右子树里递归搜
   终止条件
   当前结点为空或者是当前已经是目标数

代码

 class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
		//算自己搜
        int ret = rootSum(root, targetSum);
		//不算自己搜
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    public int rootSum(TreeNode root, long targetSum) {
        int ret = 0;

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == targetSum) {
            ret++;
        } 

        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }
}

二叉树的右视图

题目

思路

二叉树的右视图，就是每层最右面的结点排列。
当进行层次遍历时，旧队列的最后一个就是每层最右的结点。

代码

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res=new LinkedList<>();
        Queue<TreeNode> myqueue=new LinkedList<>();
        if(null==root){
            return res;
        }

        myqueue.offer(root);
        while(!myqueue.isEmpty()){
            int size=myqueue.size();
            while(size>0){
                TreeNode nownode=myqueue.poll();
                if(nownode.left!=null){
                    myqueue.offer(nownode.left);
                }

                if(nownode.right!=null){
                    myqueue.offer(nownode.right);
                }
                if(1==size){
                    res.add(nownode.val);
                }
                size--;
            }
        }


        return res;
    }
}

验证二叉搜索树

题目

思路

二叉搜索树就是进行中序遍历后呈现递增或递减的数字排序的树。
所以

思路一

中序遍历，把值保存到一个数组当中，如果数组不单调，则不是二叉搜索树

代码

class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        if(result.size()==1){
            return true;
        }

        int size=result.size();
        for(int i=1;i<size;i++){
            if(result.get(i-1)>=result.get(i)){
                return false;
            }
        }
        
        return true;

    }
}

思路二

1. 思路一只有当整个树遍历完才能得出结论，但是只要有任何子树不符合定义，就可以停止循环得出结论。
2. 不符合定义的情况就是，根比左子树中最大值小或者比右子树中最小值大。
3. 中序遍历，访问结点顺序是左中右，所以当知道根的值的时候，左子树中的最大值也已经知道了，所以可以先比较一下。那么用不用知道右子树中的最小值呢？不用。如果知道了左子树和右子树的值再和自身比较，为何不直接用后序遍历呢？

代码

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        double inorder = -Double.MAX_VALUE;
        double lastorder=Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            //Morris遍历
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
              // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root.val <= inorder) {
                return false;
            }
            inorder = root.val;
            root = root.right;
            
        }
        return true;
    }
}