二叉树定义

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

二叉树又分为其他很多种类，比如平衡二叉树，二叉查找树，红黑树，B树，2-3树等，应用也很广泛，比如mysql的b+树，hashmap的红黑树，常见的算法题，简单的就是二叉树的三种遍历，分别用循环和递归写出，中等点的，二叉树构建，镜像二叉树，二叉树高度，二叉树层次遍历，合并/反转二叉树等，难点的就是直接红黑树。。。据说都成为字节面试必考题（手动狗头）

这些题虽然都做过，长时间不做，有点忘了，正好都复习下：

1， 开胃菜：二叉树前，中，后，层次遍历

// 前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> deque = new ArrayDeque<>();
    deque.push(root);
    while (!deque.isEmpty()){
        TreeNode cur = deque.pop();
        res.add(cur.val);
        if (cur.right != null) deque.push(cur.right);
        if (cur.left != null) deque.push(cur.left);
    }
    return res;
}


// 中序遍历

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) return list;
    Deque<TreeNode> deque = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !deque.isEmpty()){
        while (cur != null){
            deque.push(cur);
            cur = cur.left;
        }
        cur = deque.pop();
        list.add(cur.val);
        cur = cur.right;
    }
    return list;
}

// 后续遍历
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) return res;
    Deque<TreeNode> deque = new ArrayDeque<>();
    deque.push(root);
    while (!deque.isEmpty()){
        TreeNode cur = deque.pop();
        res.addFirst(cur.val);
        if (cur.left != null) deque.push(cur.left);
        if (cur.right != null) deque.push(cur.right);
    }
    return res;
}

/**
 * 二叉树的层次遍历 
 * 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 *
 * 例如：
 * 给定二叉树 [3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回其自底向上的层次遍历为：
 *
 * [
 *   [15,7],
 *   [9,20],
 *   [3]
 * ]
 */
public static List<List<Integer>> levelOrderBottom(TreeNode root) {
    LinkedList<List<Integer>> result = new LinkedList<>();
    if (root == null) return result;
    Deque<TreeNode> deque = new ArrayDeque<>();
    deque.offer(root);
    while (!deque.isEmpty()) {
        int size = deque.size();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode cur = deque.poll();
            list.add(cur.val);
            if (cur.left != null) deque.offer(cur.left);
            if (cur.right != null) deque.offer(cur.right);
        }
        result.addFirst(list);
    }
    return result;
}

继续，二叉树的各种反转，长度，判断

/**
 *  二叉树的最大深度
 * 给定一个二叉树，找出其最大深度。
 *
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 *
 * 说明: 叶子节点是指没有子节点的节点
 */
public static int maxDepth2(TreeNode root) {
    if (root == null) return 0;
    int left = maxDepth2(root.left);
    int right = maxDepth2(root.right);
    return Math.max(left,right) + 1;
}

/**
 * 合并二叉树
 * 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
 */
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if(t2 == null) return t1;
    if(t1 == null) return t2;
    t1.val += t2.val;
    t1.left = mergeTrees(t1.left,t2.left);
    t1.right = mergeTrees(t1.right,t2.right);
    return t1;
}

/**
 * 左叶子之和
 * 计算给定二叉树的所有左叶子之和。
 *
 * 示例：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
 *
 *          0
 *        /  \
 *       2    4
 *     /    /  \
 *    1    3   -1
 *  / \     \    \
 * 5   1     6    8
 *
 * 返回5
 */
public class SumOfLeftLeaves {

    int sum = 0;

    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        dfs(root);
        return sum;
    }

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

}

/**
 * 把二叉搜索树转换为累加树
 * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
 * 例如：
 *
 * 输入: 原始二叉搜索树:
 *               5
 *             /   \
 *            2     13
 *
 * 输出: 转换为累加树:
 *              18
 *             /   \
 *           20     13
 */
public class ConvertBST {
    int sum = 0;
    
     /**
      * 思路要点：注意给的是二叉搜索树，如果给定的树是二叉搜索树，那么一定要从二叉搜索树的特征去思考
      *         1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
      *         2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
      *         3. 它的左、右子树也分别为二叉搜索树。
      *      二叉搜索树的中序遍历是一个单调递增的有序序列 (重点！！)
      *
      *      每个节点都要加上比自己大的节点，那么可以从最大的开始遍历，累加遍历的结果，赋值给当前节点即可，也就是倒着中序遍历
      *  @param root
      * @return
      */
     public TreeNode convertBST(TreeNode root) {
        if (root == null) return root;
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
     }
 }

暂时就这么多，下周继续druid。。。