leetcode热题100训练计划

路径总和

题index.php/tags-41973.html" >���

（）

思路

没思路，试试递归。

先分类讨论

（）

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 rightSideView(TreeNode root) {        List res=new LinkedList();        Queue 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 result = new ArrayList();        if (root == null) {            return true;        }        Stack 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=result.get(i)){                return false;            }        }                return true;    }}

思路二

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

代码

class Solution {    public boolean isValidBST(TreeNode root) {        Deque stack = new LinkedList();        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