树的遍历

144. 二叉树的前序遍历

题解思路1：递归

  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<Integer>();
  4.         preorder(root, res);
  5.         return res;
  6.     }
  8.     public void preorder(TreeNode root, List<Integer> res) {
  9.         if (root == null) {
  10.             return;
  11.         }
  12.         res.add(root.val);
  13.         preorder(root.left, res);
  14.         preorder(root.right, res);
  15.     }
  16. }

题解思路2：迭代
image.png

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }
}

94. 二叉树的中序遍历

题解思路1：递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

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

题解思路2：迭代

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

145. 二叉树的后序遍历

题解思路1：递归

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }

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

题解思路2：迭代

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node == null) continue;
            ret.add(node.val);
            stack.push(node.left);
            stack.push(node.right);
        }
        Collections.reverse(ret);
        return ret;
    }
}

注：这里有一步进行反转结果集的操作

递归

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。

题解思路：求解最大的深度，左子树深度/右子树深度的最大值+1，得到当前根节点的最大深度。

class Solution {
    public int maxDepth(TreeNode root) {
        return root==null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

后序遍历的感觉

110. 平衡二叉树

| 给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：> 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。


示例 1：
8、树 - 图2
输入：root = [3,9,20,null,null,15,7]
输出：true | | —- |

private boolean result = true;

public boolean isBalanced(TreeNode root) {
    maxDepth(root);
    return result;
}

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int l = maxDepth(root.left);
    int r = maxDepth(root.right);
    if (Math.abs(l - r) > 1) result = false;
    return 1 + Math.max(l, r);
}

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树
1
/ \
2 3
/ \
4 5

题解思路：比较暴力的想法就是遍历二叉树的所有的节点（只要左节点、右节点一直跑下去就可以了，就可以得到所有节点的结果）

private int max = 0;

public int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return max;
}

private int depth(TreeNode root) {
    if (root == null) return 0;
    int leftDepth = depth(root.left);
    int rightDepth = depth(root.right);
    max = Math.max(max, leftDepth + rightDepth);
    return Math.max(leftDepth, rightDepth) + 1;
}

注：结果返回的值是左子树+右子树的长度，是不包括中间点的

226. 翻转二叉树

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = root.left;  // 后面的操作会改变 left 指针，因此先保存下来
    root.left = invertTree(root.right);
    root.right = invertTree(left);
    return root;
}

617. 合并二叉树

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return null;
    if (t1 == null) return t2;
    if (t2 == null) return t1;
    TreeNode root = new TreeNode(t1.val + t2.val);
    root.left = mergeTrees(t1.left, t2.left);
    root.right = mergeTrees(t1.right, t2.right);
    return root;
}

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。

官方题解答案：

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        if(root.left==null&&root.right==null&&targetSum==root.val) return true;
        return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);
    }
}

自己的答案：

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(targetSum==0&&root==null)
            return false;
        return check(root,targetSum);
    }

    public boolean check(TreeNode root,int targetSum){
         //如果目标值正好为零且当前节点为叶子节点，表明存在路径满足条件。
        if(targetSum==0&&root==null)
            return true;
        //达到终止条件
        else if(root==null)
            return false;
        //递归左节点、递归右节点、返回结果
        return check(root.left,targetSum-root.val)|| check(root.right,targetSum-root.val);
    }
}

注：这样的写法没有办法通过类似【1，2】 1的用例，就是结果点为根节点，它不是完全的叶子节点。既然是叶子节点则必然满足
root.left==null&&root.right==null的条件，再则，自己想的是满足结果为0。其实结果条件可以是等于当前节点的值，依旧得出正确的结果。

437. 路径总和 III

给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1

返回 3。和等于 8 的路径有:

1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11

题解思路1：双递归模式

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return calPathSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    private int calPathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int tmp = 0;
        sum -= root.val;
        if (sum == 0) {
            tmp++;
        }
        return tmp + calPathSum(root.left, sum) + calPathSum(root.right, sum);
    }
}

题解思路2：前缀和：就是达到当前元素的路径上，之前所有元素的和。

572. 另一个树的子树

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2

给定的树 t：
4
/ \
1 2

返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

思路：凡是碰到树的问题必然是递归问题，考虑是前序、中序还是后序。这里是判断子树问题，则必然从根节点开始判断。

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null)  return false;
        return check(root,subRoot)||isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }
    public boolean check(TreeNode root,TreeNode subRoot){
        //如果susbRoot遍历完成说明满足子树的条件
        if(subRoot==null)
            return root==null;
        //如果传入的root为null，结果不满足
        if(root==null)
            return false;
        //如果两个树的值不相等则返回null
        if(root.val!=subRoot.val)
            return false;

        return check(root.left,subRoot.left)&&check(root.right,subRoot.right);
    }
}

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //对称二叉树的检查,左右节点的值是否相等？
        if(root==null)
            return true;
        return check(root.left,root.right);
    }   

    public boolean check(TreeNode root1,TreeNode root2){
        //如果都到达了null的话就可以判断是否要返回true。
        if(root1==null)
            return root2==null;
        if(root2==null)
            return root1==null;
        //检查传入的两个节点的值是否是相等的,如果不相等的话直接返回false
        if(root1.val!=root2.val)
            return false;

        return check(root1.left,root2.right)&&check(root1.right,root2.left);
    }
}

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

题解思路：判断当前二叉树的最小深度，就是在左子树和右子树之间做一个选择，选出最小深度的一边+1。递归类推即可。

class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)
            return 0;
        int left=minDepth(root.left);
        int right=minDepth(root.right);
        if(left==0) 
            return right+1;
        if(right==0) 
            return left+1;
        return Math.min(left,right)+1;
    }
}

注：使用层序遍历的话效率会更高。因为使用递归的方式，相当于在DFS获取所有的路径，但是BFS则到达最短就会停止。

404. 左叶子之和

计算给定二叉树的所有左叶子之和。

class Solution {
    private static int count;
    public int sumOfLeftLeaves(TreeNode root) {
        sum(root);
        return count;
    }

    public void sum(TreeNode root){
        if(root==null) return;
        sum(root.left);
        if(root.left!=null&&root.left.left==null&&root.left.right==null)
            count+=root.left.val;
        sum(root.right);
    }
}

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;
    if (isLeaf(root.left)) return root.left.val + sumOfLeftLeaves(root.right);
    return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}

private boolean isLeaf(TreeNode node){
    if (node == null) return false;
    return node.left == null && node.right == null;
}

687. 最长同值路径

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。

题解思路：寻找当前路径同值的节点，那么优先想到的是使用后序遍历的方式，因为我们先遍历左右节点才能拿它们的值和根节点比较判断值是不是相等的。

private int path = 0;

public int longestUnivaluePath(TreeNode root) {
    dfs(root);
    return path;
}

private int dfs(TreeNode root){
    if (root == null) return 0;
    int left = dfs(root.left);
    int right = dfs(root.right);
    int leftPath = root.left != null && root.left.val == root.val ? left + 1 : 0;
    int rightPath = root.right != null && root.right.val == root.val ? right + 1 : 0;
    path = Math.max(path, leftPath + rightPath);
    return Math.max(leftPath, rightPath);
}

注：只能是在一条路劲上，不可以同时包含左右节点

337. 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]

3
/ \
2 3
\ \
3 1

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

题解思路：每个节点都有偷和不偷的两种选择方式。考虑对于当前节点来说对于其他节点的影响。如果当前节点偷了，那么它的子节点必定不能偷。如果当前节点没有偷，那么子节点可偷可不偷，获取最大值就可以了。

public class Solution {

    // 树的后序遍历

    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }

        // 分类讨论的标准是：当前结点偷或者不偷
        // 由于需要后序遍历，所以先计算左右子结点，然后计算当前结点的状态值
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        // dp[0]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点不偷
        // dp[1]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点偷
        int[] dp = new int[2];

        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        dp[1] = node.val + left[0] + right[0];
        return dp;
    }
}

671. 二叉树中第二小的节点

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
更正式地说，root.val = min(root.left.val, root.right.val) 总成立。

题解思路：左右节点递归，找到大于根节点的值就可以立即返回，否则就知道null返回-1.

class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if(root==null) return -1;
        return  help(root,root.val);
    }

    private int help(TreeNode root, int min) {
        //遍历到最后仍然没有得到结果就返回-1；
        if(root==null) return -1;
        //如果当前节点大于根节点就可以返回结果了
        if(root.val>min) return root.val;
        int left=help(root.left,min);
        int right=help(root.right,min);
        if(left==-1) return right;
        if(right==-1) return left;
        return Math.min(left,right);
    }
}

层次遍历

637. 二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
示例 1：
输入：
3
/ \
9 20
/ \
15 7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

题解思路：层序遍历+平均值求解

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Double> res = new ArrayList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            double sum = 0.0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            res.add(sum / size);
        }
        return res;
    }
}

513. 找树左下角的值

给定一个二叉树，在树的最后一行找到最左边的值。
题解思路：记录每一层第一个元素即可

public int findBottomLeftValue(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        root = queue.poll();
        if (root.right != null) queue.add(root.right);
        if (root.left != null) queue.add(root.left);
    }
    return root.val;
}

BST

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：
8、树 - 图3
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

题解思路：前序遍历，判断当前节点的情况。如果大于最大值就往左边递归找更小的值，如果小于最小值就往右边递归找寻更大的值，否则的话继续递归就好了

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        //这一步就相当于在判断节点符不符合要求，然后进行剪枝操作。
        if (root.val > high) return trimBST(root.left, low, high);
        if (root.val < low) return trimBST(root.right, low, high);

        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

230. 二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：
8、树 - 图4
输入：root = [3,1,4,null,2], k = 1
输出：1

题解思路1：中序遍历二叉搜索树得到的结果是按序排列的。

class Solution {
    private static int res;
    private static int count;//记录遍历到哪个中间节点
    public int kthSmallest(TreeNode root, int k) {
        search(root,k);
        return res;
    }

    public void search(TreeNode root,int k){
        if(root==null)  return;
        search(root.left,k);
        count++;
        if(count==k){//因为k值在每一个递归调用的方法中都存有拷贝值，所以不可以使用k来判断
            res=root.val;
            return;//找到结果终止寻找
        }
        search(root.right,k);
    }
}

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
8、树 - 图5

示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2和节点 8的最近公共祖先是 6。		 
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       if(root.val>p.val&&root.val>q.val)
            return lowestCommonAncestor(root.left,p,q);
        if(root.val<p.val&&root.val<q.val)
           return lowestCommonAncestor(root.right,p,q);
        return root;
    }
}

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
8、树 - 图6
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5和节点 1的最近公共祖先是节点 3 。		 
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)
            return null;
        if(root==p||root==q)
            return root;
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);

        if(left==null)  return right;
        if(right==null) return left;
        return root;
    }
}

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：
8、树 - 图7输入：nums = [-10,-3,0,5,9]输出：[0,-3,9,-10,null,5]解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：8、树 - 图8

题解思路：其实这道题仔细想的话是二分查找算法一样的。关注选择的区间，关注如何移动，关注终止条件。

题解思路1：选择区间为左闭右开

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        //这样的调用方式，选择的区间为左闭右开。[left，right);
        return sortedArrayToBST(nums,0,nums.length);
    }

    public TreeNode sortedArrayToBST(int[] nums,int start,int end) {
        //在左闭右开的选择区间内，只有当start<end时内部才有有效值。例如[left，left)是没有有效的值的。
        if(start>=end)  return null;
        //二分选择中间的节点
        int mid=(start+end)/2;
        //创建新节点
        TreeNode newHead=new TreeNode(nums[mid]);
        //二分区间,还是从选择的区间入手考虑，右边界是开，取不到的，所以选择mid
        newHead.left=sortedArrayToBST(nums,start,mid);
        //二分区间,还是从选择的区间入手考虑，左边边界是闭，要是能够取到的，所以选择mid+1；
        newHead.right=sortedArrayToBST(nums,mid+1,end);
        return  newHead;
    }
}

题解思路2：选择区间为左闭右闭

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        //这样的调用方式，选择的区间为左闭右闭。[left，right];
        return sortedArrayToBST(nums,0,nums.length-1);
    }

    public TreeNode sortedArrayToBST(int[] nums,int start,int end) {
        if(start>end)  return null;
        //二分选择中间的节点
        int mid=(start+end)/2;
        //创建新节点
        TreeNode newHead=new TreeNode(nums[mid]);
        newHead.left=sortedArrayToBST(nums,start,mid-1);
        newHead.right=sortedArrayToBST(nums,mid+1,end);
        return  newHead;
    }
}

109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

0
/ \
-3 9
/ /
-10 5

题解思路：
参考Leetcode108的方式，找寻中间节点，然后分为左右两部分节点，递归执行即可。
1、链表中间节点的寻找方式
2、终止条件怎么写。这里终止条件有两个分别是限制左边界和右边界的。

因为根据我的递归调用方式，左节点永远不会为null。所以当只有一个节点的时候返回。

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        //终止条件（主要用于限制右边界）
        if(head==null) return null;
        //主要用于限制左边界
        if(head.next==null) return new TreeNode(head.val);

        //找寻中间链表
        ListNode slow=head;
        ListNode fast=head;
        ListNode pre=head;
        while(fast!=null&&fast.next!=null){
            pre=slow;//始终保证有一个指针指向slow链表节点的前面，用于分割链表
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode mid=slow;
        //根据中间链表节点的值创捷树节点
        TreeNode newHead=new TreeNode(mid.val);

        pre.next=null;
        newHead.left= sortedListToBST(head);
        newHead.right= sortedListToBST(mid.next);
        return newHead;
    }
}

98. 验证二叉搜索树

| 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true | | —- |

二叉搜索树的中序遍历结果必为升序序列

class Solution {
    List<Integer> res = new ArrayList<Integer>();

    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        inOrder(root);

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

    public void inOrder(TreeNode root) {
        if (root == null)
            return;
        inOrder(root.left);
        res.add(root.val);
        inOrder(root.right);
    }
}

优化版：直接在递归的过程中比较

class Solution {
    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;

        if (!isValidBST(root.left))
            return false;

        if (root.val <= pre)
            return false;

        pre = root.val;

        return isValidBST(root.right);
    }
}

114. 二叉树展开为链表

| 给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
- 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：
8、树 - 图9
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6] | | —- |

题解思路：关注根节点应该怎么做。

class Solution {
    public void flatten(TreeNode root) {
        if (root == null)
            return ;
        flatten(root.left);
        flatten(root.right);            

        TreeNode left = root.left;
        TreeNode right = root.right;

        root.left = null;
        root.right = left;

        while (root.right != null)
            root = root.right;
        root.right = right;
    }
}

124. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：
8、树 - 图10
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6		 
class Solution {
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        //审题：寻找最大的路径，无论这个路径是从左到右还是从右到左其实都没有影响，因为需要的其实只是路径上的值而已。
        //遍历所有的路径。每一个节点返回的路径应该是左右子节点路径的最大值（可能为负数）加上自身的数值
        maxPath(root);
        return max;
    }

    public int maxPath(TreeNode root) {
        if (root == null)
            return 0;
        int left = maxPath(root.left);
        int right = maxPath(root.right);
        //注意这里需要判断，如果左右节点的和小于0的话，不加上
        int cur = (left > 0 ? left : 0) + (right > 0 ? right : 0) + root.val;
        max = Math.max(max, cur);
        return Math.max(left > 0 ? left : 0, right > 0 ? right : 0) + root.val;
    }
}

注意解题过程中负数的处理