二叉树Tag

二叉树理论基础
二叉树的种类
二叉树的遍历方式
二叉树的定义
……

二叉树

二叉树理论基础篇

二叉树的种类

在我们解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树。
- 满二叉树：如果一棵二叉树只有度为 0 的结点和度为 2 的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树。
- 完全二叉树的定义如下：在完全二叉树中，除了最底层结点可能没填满外，其余每层结点数都达到最大值，并且最下面一层的结点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个结点。
前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
平衡二叉搜索树：又被称为 AVL 树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。如图：

二叉树的遍历方式

二叉树主要有两种遍历方式：
- 深度优先遍历：先往深走，遇到叶子结点再往回走。
  - 前序遍历（递归法，迭代法）
  - 中序遍历（递归法，迭代法）
  - 后序遍历（递归法，迭代法）
- 广度优先遍历：一层一层的去遍历。
  - 层次遍历（迭代法）
最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。
- 之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。
- 而广度优先遍历的实现一般使用队列来实现

二叉树的定义

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

1.二叉树的递归遍历

★递归三部曲

这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！
1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件： 写完了递归算法，运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。

前序遍历：

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

    public List<Integer> preorderTraversal(TreeNode root) {
        // 递归终止条件
        if (root == null) {
            return result;
        }
        // 前序遍历：中左右
        result.add(root.val);
        result = preorderTraversal(root.left);
        result = preorderTraversal(root.right);
        return result;
    }
}

中序遍历：

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

    public List<Integer> inorderTraversal(TreeNode root) {
        // 递归终止条件
        if (root == null) {
            return result;
        }
        // 中序遍历：左中右
        result = inorderTraversal(root.left);
        result.add(root.val);
        result = inorderTraversal(root.right);
        return result;
    }
}

后序遍历：

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

    public List<Integer> postorderTraversal(TreeNode root) {
        // 递归终止条件
        if (root == null) {
            return result;
        }
        // 后序遍历：左右中
        result = postorderTraversal(root.left);
        result = postorderTraversal(root.right);
        result.add(root.val);
        return result;
    }
}

2.二叉树的迭代遍历(栈)

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。那用栈也是可以实现二叉树的前中后序遍历的。

前序遍历：

先看一下前序遍历。
- 前序遍历是中左右，每次先处理的是中间结点，那么先将根结点放入栈中，然后将右孩子加入栈，再加入左孩子。
- 为什么要先加入右孩子，再加入左孩子呢？因为这样出栈的时候才是中左右的顺序。

class Solution {
    private List<Integer> result = new ArrayList<>();
    private Deque<TreeNode> deque = new ArrayDeque<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) { // 如果root为null，直接返回
            return result;
        }
        deque.push(root);
        while (!deque.isEmpty()) {
            // 根结点先出栈
            TreeNode node = deque.pop();
            result.add(node.val);
            // 先压栈右结点，再压栈左结点，才能保证前序遍历的顺序
            if (node.right != null) {
                deque.push(node.right);
            }
            if (node.left != null) {
                deque.push(node.left);
            }
        }
        return result;
    }
}

中序遍历：

中序遍历的逻辑和前序遍历不同，在前序遍历中，先访问的元素是中间结点，要处理的元素也是中间结点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间结点。
- 中序遍历是左中右，先访问的是二叉树顶部的结点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理结点（也就是在把结点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
我们可以这样做：
- 先把根结点入栈，然后每次结点出栈的时候，如果是第一次出栈，则按照右结点、当前结点、左结点的顺序入栈，如果是第二次出栈，则输出。

class Solution {
    private List<Integer> result = new ArrayList<>();
    private List<TreeNode> temp = new ArrayList<>(); // 用于查看结点是否是第一次出栈
    private Deque<TreeNode> deque = new ArrayDeque<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) { // 先排除特殊情况
            return result;
        }
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            if (!temp.contains(node)) { // 结点是第一次出栈
                temp.add(node);
                // 如果结点是第一次出栈，就按照node.right，node，node.left的顺序入栈
                if (node.right != null) {
                    deque.push(node.right);
                }
                deque.push(node);
                if (node.left != null) {
                    deque.push(node.left);
                }
            } else { // 结点是第二次出栈
                result.add(node.val);
            }
        }
        return result;
    }
}

后序遍历：

后序遍历和中序遍历大同小异，它的处理顺序和访问顺序也是不一致的。
我们可以这样做：
- 先把根结点入栈，然后每次结点出栈的时候，如果是第一次出栈，则按照当前结点、右结点、左结点的顺序入栈，如果是第二次出栈，则输出。

class Solution {
    private List<Integer> result = new ArrayList<>();
    private List<TreeNode> temp = new ArrayList<>(); // 用于查看结点是否是第一次出栈
    private Deque<TreeNode> deque = new ArrayDeque<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) { // 先排除特殊情况
            return result;
        }
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            if (!temp.contains(node)) { // 结点是第一次出栈
                temp.add(node);
                // 如果结点是第一次出栈，就按照node，node.right，node.left的顺序入栈
                deque.push(node);
                if (node.right != null) {
                    deque.push(node.right);
                }
                if (node.left != null) {
                    deque.push(node.left);
                }
            } else { // 结点是第二次出栈
                result.add(node.val);
            }
        }
        return result;
    }
}

还有第二种解法：
- 后序遍历是：左右中；前序遍历是：中左右。
  - 那我们可以按前序遍历的解法，先把 result 中的顺序调整为 “中右左”，然后再把 result 反转就变为了 “左右中”。

class Solution {
    private List<Integer> result = new ArrayList<>();
    private Deque<TreeNode> deque = new ArrayDeque<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        // 先排除特殊情况
        if (root == null) {
            return result;
        }
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            result.add(node.val);
            if (node.left != null) {
                deque.push(node.left);
            }
            if (node.right != null) {
                deque.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

总结：
- 可以看出前序和中序是完全两种代码风格，并不像递归写法那样代码稍做调整，就可以实现前后中序。
  - 这是因为前序遍历中访问结点（遍历结点）和处理结点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！

3.二叉树的统一迭代法

二叉树的统一迭代法就在于判断当前弹栈元素是不是第一次弹栈，如果是第一次弹栈，就要进行相应的再压栈处理，否则就输出到结果集中。

可以看到前中后序遍历的实现代码都可以是大同小异的：

前序遍历：

class Solution {
    private List<Integer> result = new ArrayList<>();
    private List<TreeNode> temp = new ArrayList<>(); // 用于查看结点是否是第一次出栈
    private Deque<TreeNode> deque = new ArrayDeque<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) { // 先排除特殊情况
            return result;
        }
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            if (!temp.contains(node)) { // 结点是第一次出栈
                temp.add(node);
                // 如果结点是第一次出栈，就按照node.right，node.left，node的顺序入栈
                if (node.right != null) {
                    deque.push(node.right);
                }
                if (node.left != null) {
                    deque.push(node.left);
                }
                deque.push(node);
            } else { // 结点是第二次出栈
                result.add(node.val);
            }
        }
        return result;
    }
}

中序遍历：

class Solution {
    private List<Integer> result = new ArrayList<>();
    private List<TreeNode> temp = new ArrayList<>(); // 用于查看结点是否是第一次出栈
    private Deque<TreeNode> deque = new ArrayDeque<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) { // 先排除特殊情况
            return result;
        }
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            if (!temp.contains(node)) { // 结点是第一次出栈
                temp.add(node);
                // 如果结点是第一次出栈，就按照node.right，node，node.left的顺序入栈
                if (node.right != null) {
                    deque.push(node.right);
                }
                deque.push(node);
                if (node.left != null) {
                    deque.push(node.left);
                }
            } else { // 结点是第二次出栈
                result.add(node.val);
            }
        }
        return result;
    }
}

后序遍历：

class Solution {
    private List<Integer> result = new ArrayList<>();
    private List<TreeNode> temp = new ArrayList<>(); // 用于查看结点是否是第一次出栈
    private Deque<TreeNode> deque = new ArrayDeque<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) { // 先排除特殊情况
            return result;
        }
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            if (!temp.contains(node)) { // 结点是第一次出栈
                temp.add(node);
                // 如果结点是第一次出栈，就按照node，node.right，node.left的顺序入栈
                deque.push(node);
                if (node.right != null) {
                    deque.push(node.right);
                }
                if (node.left != null) {
                    deque.push(node.left);
                }
            } else { // 结点是第二次出栈
                result.add(node.val);
            }
        }
        return result;
    }
}

4.二叉树的层序遍历(队列)

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
- 需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

层序遍历的万用模板

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private ArrayDeque<TreeNode> deque = new ArrayDeque<>(); // 辅助队列

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) { // 排除特殊情况
            return result;
        }
        deque.addLast(root);
        while (!deque.isEmpty()) {
            List<Integer> itemList = new ArrayList<>(); // 保存每一层的结果
            int len = deque.size(); // 用于判断当前层是不是遍历完了
            while (len > 0) {
                TreeNode node = deque.removeFirst();
                itemList.add(node.val);
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
                len--;
            }
            result.add(itemList);
        }
        return result;
    }
}

4.1 二叉树的层次遍历II

题目

给你二叉树的根结点 root ，返回其结点值 自底向上的层序遍历 。（即按从叶子结点所在层到根结点所在的层，逐层从左向右遍历）
示例 1：
1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：
1
2
输入：root = [1]
输出：[[1]]
示例 3：
1
2
输入：root = []
输出：[]
提示：
- 树中结点数目在范围 [0, 2000] 内
- -1000 <= Node.val <= 1000

思路

就是在 4.二叉树的层序遍历 的基础上，增加一个 Collections.reverse() 方法而已。

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private ArrayDeque<TreeNode> deque = new ArrayDeque<>();

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) { // 排除特殊情况
            return result;
        }
        deque.addLast(root);
        while (!deque.isEmpty()) {
            List<Integer> itemList = new ArrayList<>();
            int len = deque.size();
            while (len > 0) {
                TreeNode node = deque.removeFirst();
                itemList.add(node.val);
                if (node.left != null) {
                    deque.add(node.left);
                }
                if (node.right != null) {
                    deque.add(node.right);
                }
                len--;
            }
            result.add(itemList);
        }
        Collections.reverse(result);
        return result;
    }
}

4.2 二叉树的右视图

题目

给定一个二叉树的 根结点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的结点值。
示例 1:
1
2
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
1
2
输入: [1,null,3]
输出: [1,3]
示例 3:
1
2
输入: []
输出: []
提示:
- 二叉树的结点个数的范围是 [0,100]
- -100 <= Node.val <= 100

思路

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进 result 数组中，随后返回 result 就可以了。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) { // 排除特殊情况
            return result;
        }
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int len = deque.size(); // 记录当前层级的元素个数
            while (len > 0) {
                TreeNode node = deque.removeFirst();
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
                len--;
                if (len == 0) { // len为0表示是当前层级的最后一个元素
                    result.add(node.val);
                }
            }
        }
        return result;
    }
}

4.3 二叉树的层平均值

题目

给定一个非空二叉树的根结点 root , 以数组的形式返回每一层结点的平均值。与实际答案相差 10^(-5) 以内的答案可以被接受。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

示例 2:

1 2	输入：root = [3,9,20,15,7] 输出：[3.00000,14.50000,11.00000]

提示：

树中结点数量在 [1, 104] 范围内
-2^31 <= Node.val <= 2^31 - 1

思路

本题就是层序遍历的时候把一层求个总和在取一个均值。

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        if (root == null) { // 排除特殊情况
            return result;
        }
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int len = deque.size(); // 用于判断当前层级是否遍历完
            int num = len; // 用于计算平均数
            double sum = 0; // 用于计算当前层的总和
            while (len > 0) {
                TreeNode node = deque.removeFirst();
                sum += node.val;
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
                len--;
            }
            result.add(sum / num);
        }
        return result;
    }
}

4.4 N叉树的层序遍历

题目

给定一个 N 叉树，返回其结点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子结点都由 null 值分隔（参见示例）。
示例 1：
1
2
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
示例 2：
1
2
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
提示：
- 树的高度不会超过 1000
- 树的结点总数在 [0, 10^4] 之间

思路

这道题依旧是模板题，只不过一个结点有多个孩子了。

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        ArrayDeque<Node> deque = new ArrayDeque<>();
        if (root == null) { // 排除特殊情况
            return result;
        }
        deque.addLast(root);
        while (!deque.isEmpty()) {
            List<Integer> itemList = new ArrayList<>();
            int len = deque.size();
            while (len > 0) {
                Node node = deque.removeFirst();
                itemList.add(node.val);
                List<Node> children = node.children;
                for (int i = 0; i < children.size(); i++) {
                    deque.addLast(children.get(i));
                }
                len--;
            }
            result.add(itemList);
        }
        return result;
    }
}

4.5 在每个树行中找最大值

题目

给定一棵二叉树的根结点 root ，请找出该二叉树中每一层的最大值。
示例1：
1
2
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2：
1
2
输入: root = [1,2,3]
输出: [1,3]
提示：
- 二叉树的结点个数的范围是 [0,104]
- -2^31 <= Node.val <= 2^31 - 1

思路

层序遍历，取每一层的最大值。

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        if (root == null) { // 排除特殊情况
            return result;
        }
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int max = Integer.MIN_VALUE;
            int len = deque.size(); // 用于判断当前层是否遍历完
            while (len > 0) {
                TreeNode node = deque.removeFirst();
                if (node.val > max) {
                    max = node.val;
                }
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
                len--;
            }
            result.add(max);
        }
        return result;
    }
}

4.6 填充每个结点的下一个右侧结点指针II

题目

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧结点。如果找不到下一个右侧结点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

1
2
3

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧结点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例 2：

1 2	输入：root = [] 输出：[]

提示：

树中的结点数在范围 [0, 6000] 内
-100 <= Node.val <= 100

思路

依然套用层序遍历的模板，只不过要注意当 len 为 0 时，要让当前出队的结点的 next 指向 null。

class Solution {
    public Node connect(Node root) {
        ArrayDeque<Node> deque = new ArrayDeque<>();
        if (root == null) { // 排除特殊情况
            return null;
        }
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int len = deque.size();
            while (len > 0) {
                Node n1 = deque.removeFirst();
                Node n2 = deque.peekFirst();
                if (n1.left != null) {
                    deque.addLast(n1.left);
                }
                if (n1.right != null) {
                    deque.addLast(n1.right);
                }
                len--;
                if (len == 0) {
                    n1.next = null;
                } else {
                    n1.next = n2;
                }
            }
        }
        return root;
    }
}

4.7 二叉树的最大深度

题目

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根结点到最远叶子结点的最长路径上的结点数。
示例 1：
1
2
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
1
2
输入：root = [1,null,2]
输出：2
提示：
- 树中结点的数量在 [0, 10^4] 区间内。
- -100 <= Node.val <= 100

思路

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度。

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) { // 排除特殊情况
            return 0;
        }
        int result = 0;
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int len = deque.size();
            while (len > 0) {
                TreeNode node = deque.removeFirst();
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
                len--;
                if (len == 0) {
                    result += 1;
                }
            }
        }
        return result;
    }
}

递归法：

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getDepth(root, 1);
    }

    public int getDepth(TreeNode node, int depth) {
        int leftDepth, rightDepth;
        leftDepth = rightDepth = depth;
        if (node.left == null && node.right == null) {
            return depth;
        }
        if (node.left != null) {
            leftDepth = getDepth(node.left, depth + 1);
        }
        if (node.right != null) {
            rightDepth = getDepth(node.right, depth + 1);
        }
        return Math.max(leftDepth, rightDepth);
    }
}

4.8 二叉树的最小深度

题目

给定一个二叉树，找出其最小深度。
最小深度是从根结点到最近叶子结点的最短路径上的结点数量。
说明：叶子结点是指没有子结点的结点。
示例 1：
1
2
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
1
2
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
提示：
- 树中结点数的范围在 [0, 105] 内
- -1000 <= Node.val <= 1000

思路

相对于 4.7 二叉树的最大深度，本题还也可以使用层序遍历的方式来解决，思路是一样的。

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int result = 0;
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int len = deque.size();
            while (len > 0) {
                TreeNode node = deque.removeFirst();
                // 左右子结点都为空，表示已经到最小深度处了
                if (node.left == null && node.right == null) {
                    result++;
                    return result;
                }
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
                len--;
                if (len == 0) {
                    result++;
                }
            }
        }
        return result;
    }
}

递归法：

class Solution {
    private int result = Integer.MAX_VALUE;

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getDepth(root, 1);
        return result;
    }

    public void getDepth(TreeNode root, int depth) {
        if (root.left == null && root.right == null) {
            result = Math.min(result, depth);
            return;
        }
        if (root.left != null) {
            getDepth(root.left, depth + 1);
        }
        if (root.right != null) {
            getDepth(root.right, depth + 1);
        }
    }
}

5.翻转二叉树

题目

给你一棵二叉树的根结点 root ，翻转这棵二叉树，并返回其根结点。
示例 1：
1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
1
2
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
1
2
输入：root = []
输出：[]
提示：
- 树中结点数目范围在 [0, 100] 内
- -100 <= Node.val <= 100

思路

想要翻转二叉树，其实就把每一个结点的左右孩子交换一下就可以了。遍历的过程中去翻转每一个结点的左右孩子就可以达到整体翻转的效果。

关键在于遍历顺序，前中后序或层序应该选哪一种遍历顺序？
这道题目使用前序遍历、后序遍历、层序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些结点的左右孩子翻转了两次！建议拿纸画一画，就理解了。

我这里用的是层序遍历：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        ArrayDeque<TreeNode> deque = new ArrayDeque<>(); // 用于判断树是否遍历完了
        deque.addLast(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.removeFirst();
            TreeNode left = null;
            TreeNode right = null;
            if (node.left != null) {
                left = node.left;
                deque.addLast(left);
            }
            if (node.right != null) {
                right = node.right;
                deque.addLast(right);
            }
            node.left = right;
            node.right = left;
        }
        return root;
    }
}

用递归也能做：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 递归三要素：
        //  1.确定传入的参数和返回值
        //  2.确定递归终止条件
        //  3.确定单层业务逻辑
        // 递归终止条件
        if (root == null) {
            return root;
        }
        // 这里用的是后序遍历
        TreeNode temp = root.right;
        root.right = invertTree(root.left);
        root.left = invertTree(temp);
        return root;
    }
}

但是递归比较玄学，我还是喜欢用迭代。

6.对称二叉树

题目

给你一个二叉树的根结点 root ，检查它是否轴对称。
示例 1：
1
2
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
1
2
输入：root = [1,2,2,null,3,null,3]
输出：false
提示：
- 树中结点数目在范围 [1, 1000] 内
- -100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？

思路

首先想清楚，判断对称二叉树要比较的是哪两个结点，要比较的可不是父结点的左右子结点！

对于二叉树是否对称，要比较的是根结点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根结点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。

因此我们要通过递归函数的返回值来判断两个子树的内侧结点和外侧结点是否相等。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode leftNode, TreeNode rightNode) {
        // 1.确定传入参数和返回值
        // 2.确定递归终止的条件
        // 3.确定单次递归的逻辑
        if (leftNode == null && rightNode == null) {
            return true;
        } else if (leftNode == null && rightNode != null) {
            return false;
        } else if (leftNode != null && rightNode == null) {
            return false;
        } else if (leftNode.val != rightNode.val) { // 左右两个结点都不为空
            return false;
        } else { // 左右两个结点都不为空且值相等
            boolean compareIn, compareOut;
            compareIn = compare(leftNode.right, rightNode.left); // 比较内侧
            compareOut = compare(leftNode.left, rightNode.right); // 比较外侧
            return compareIn && compareOut;
        }
    }
}

这题也可以用迭代来做。

可以考虑用层序遍历的思想来做，对每一层都判断其是否对称，遍历到其中一层不对称就结束循环，或者直到遍历完整棵树。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode leftNode = queue.poll();
            TreeNode rightNode = queue.poll();
            if (leftNode == null && rightNode == null) {
            } else if (leftNode != null && rightNode == null) {
                return false;
            } else if (leftNode == null && rightNode != null) {
                return false;
            } else if (leftNode.val != rightNode.val) { // 两个结点都不为空
                return false;
            } else { // 两个结点都不为空且值相同
                // 外侧结点
                queue.offer(leftNode.left);
                queue.offer(rightNode.right);
                // 内侧结点
                queue.offer(leftNode.right);
                queue.offer(rightNode.left);
            }
        }
        return true;
    }
}

7.平衡二叉树

题目

给定一个二叉树，判断它是否是平衡二叉树。
示例 1：
1
2
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
1
2
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
1
2
输入：root = []
输出：true
提示：
- 树中的结点数在范围 [0, 5000] 内
- -104 <= Node.val <= 104

思路

这里强调一波概念：
- 二叉树结点的深度：指从根结点到该结点的最长简单路径边的条数。
- 二叉树结点的高度：指从该结点到叶子结点的最长简单路径边的条数。
如图：
- 因为求深度可以从上到下去查，所以需要前序遍历（中左右）
  而求高度只能从下到上去查，所以只能后序遍历（左右中）

递归三步曲分析：

明确递归函数的参数和返回值
- 参数：当前传入结点、当前传入结点的深度。返回值：以当前传入结点为根结点的树的深度。
  那么如何标记左右子树是否差值大于 1 呢？
  如果当前传入结点为根结点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
  所以如果已经不是二叉平衡树了，可以返回 -1 来标记已经不符合平衡树的规则了。
明确终止条件
- 递归的过程中如果左右子结点都为 null，表示当前结点是叶子结点，就返回当前结点的深度。
明确单层递归的逻辑
- 如何判断以当前传入结点为根结点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。
  分别求出其左右子树的高度，然后如果差值小于等于 1，则返回当前二叉树的高度，否则返回 -1，表示已经不是二叉平衡树了。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return getDepth(root, 1) != -1;
    }

    public int getDepth(TreeNode node, int depth) {
        int leftDepth, rightDepth;
        leftDepth = rightDepth = depth;
        if (node.left == null && node.right == null) {
            return depth;
        }
        if (node.left != null) {
            leftDepth = getDepth(node.left, depth + 1);
        }
        if (leftDepth == -1) {
            return -1;
        }
        if (node.right != null) {
            rightDepth = getDepth(node.right, depth + 1);   
        }
        if (rightDepth == -1) {
            return -1;
        }
        if (Math.abs(leftDepth - rightDepth) > 1) { // 用-1表示已经不是平衡二叉树了
            return -1;
        } else {
            return Math.max(leftDepth, rightDepth);
        }
    }
}

8.二叉树的所有路径

题目

给你一个二叉树的根结点 root ，按 任意顺序 ，返回所有从根结点到叶子结点的路径。
叶子结点 是指没有子结点的结点。
示例 1：
1
2
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
示例 2：
1
2
输入：root = [1]
输出：["1"]
提示：
- 树中结点的数目在范围 [1, 100] 内
- -100 <= Node.val <= 100

思路

这道题目要求从根结点到叶子的路径，所以需要前序遍历，这样才方便让父结点指向孩子结点，找到对应的路径。

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

前序遍历以及回溯的过程如图：

257.二叉树的所有路径

我们先使用递归的方式，来做前序遍历。要知道递归和回溯就是一家的，本题也需要回溯。

 // 递归三步走：
 // 1.确定传入的参数和返回的值
 // 2.确定递归终止的条件
 // 3.确定递归的单层逻辑
class Solution {
    private List<String> result = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        List<Integer> path = new ArrayList<>(); // path用于记录当前已经走过的结点
        if (root == null) {
            return result;
        }
        searchTreePath(root, path);
        return result;
    }

    // 前序遍历来遍历路径
    public void searchTreePath(TreeNode node, List<Integer> path) {
        path.add(node.val);
        if (node.left == null && node.right == null) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < path.size() - 1; i++) {
                sb.append(path.get(i)).append("->");
            }
            sb.append(path.get(path.size() - 1));
            result.add(sb.toString());
            return;
        }
        if (node.left != null) {
            searchTreePath(node.left, path);
            path.remove(path.size() - 1); // 回溯
        }
        if (node.right != null) {
            searchTreePath(node.right, path);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

迭代法也可以做，但是明显性能不如递归+回溯。

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) { // 排除特殊情况
            return result;
        }
        Deque<Object> deque = new LinkedList<>();
        // 结点和路径同时入栈
        deque.push(root);
        deque.push(root.val + "");
        while (!deque.isEmpty()) {
            // 结点和路径同时出栈
            String path = (String) deque.pop();
            TreeNode node = (TreeNode) deque.pop();
            if (node.left == null && node.right == null) {
                result.add(path);
            }
            if (node.left != null) {
                deque.push(node.left);
                deque.push(path + "->" + node.left.val);
            }
            if (node.right != null) {
                deque.push(node.right);
                deque.push(path + "->" + node.right.val);
            }
        }
        return result;
    }
}

注意这里结点和路径同时入栈出栈。

9.二叉搜索树中的搜索

题目

给定二叉搜索树（BST）的根结点 root 和一个整数值 val。
你需要在 BST 中找到结点值等于 val 的结点。返回以该结点为根的子树。如果结点不存在，则返回 null 。
示例 1:
1
2
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]
示例 2:
1
2
输入：root = [4,2,7,1,3], val = 5
输出：[]
提示：
- 树中结点数在 [1, 5000] 范围内
- 1 <= Node.val <= 107
- root 是二叉搜索树
- 1 <= val <= 107

思路

根据二叉搜索树的特性解题：

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode node = root;
        while (node != null) {
            if (node.val == val) {
                return node;
            } else if (node.val > val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return null;
    }
}

10.验证二叉搜索树

题目

给你一个二叉树的根结点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
- 结点的左子树只包含小于当前结点的数。
- 结点的右子树只包含大于当前结点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
1
2
输入：root = [2,1,3]
输出：true
示例 2：
1
2
3
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根结点的值是 5 ，但是右子结点的值是 4 。
提示：
- 树中结点数目范围在[1, 10^4] 内
- -2^31 <= Node.val <= 2^31 - 1

思路

中序遍历下，输出的二叉搜索树结点的数值是有序序列。有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

可以递归中序遍历将二叉搜索树转变成一个数组，然后只要比较一下，这个数组是否是有序的，注意二叉搜索树中不能有重复元素。

class Solution {
    private List<Integer> list = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        inOrderTraversal(root);
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) >= list.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    public void inOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrderTraversal(node.left);
        list.add(node.val);
        inOrderTraversal(node.right);
    }
}

这题也可以用递归来做：

这道题目比较容易陷入一个陷阱：
不能单纯的比较左结点小于中间结点，右结点大于中间结点就完事了。然后写出这样的代码：
1
2
3
4
5
6
if (root.left != null && root.left.val >= root.val) {
return false;
}
if (root.right != null && root.right.val <= root.val) {
return false;
}
我们要比较的是左子树所有结点小于中间结点，右子树所有结点大于中间结点。所以以上代码的判断逻辑是错误的。例如： [10,5,15,null,null,6,20] 这个 case，结点 10 大于左结点 5，小于右结点 15，但右子树里出现了一个 6，这就不符合了：

正确的递归代码如下：

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

    public boolean isValidBST(TreeNode node, long upper, long low) {
        if (node == null) {
            return true;
        }
        if (node.val >= upper || node.val <= low) {
            return false;
        }
        // 左子树所有结点小于中间结点，右子树所有结点大于中间结点
        return isValidBST(node.left, node.val, low) && isValidBST(node.right, upper, node.val);
    }
}

11.二叉搜索树中的插入操作

题目

给定二叉搜索树（BST）的根结点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根结点。输入数据保证新值和原始二叉搜索树中的任意结点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回 任意有效的结果 。
示例 1：
1
2
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
示例 2：
1
2
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]
示例 3：
1
2
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]
提示：
- 树中的结点数将在 [0, 104]的范围内。
- -10^8 <= Node.val <= 10^8
- 所有值 Node.val 是 独一无二 的。
- -10^8 <= val <= 10^8
- 保证 val 在原始 BST 中不存在。

思路

就是利用搜索树的特性，找到要插入的地方，当然别忘了记录父结点的位置，否则无法实现插入：

// 迭代法
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val, null, null);
        }
        TreeNode node, parent; // parent用于记录node的上一个位置
        parent = node = root;
        while (node != null) {
            parent = node;
            if (node.val < val) {
                node = node.right;
            } else if (node.val > val) {
                node = node.left;
            }
        }
        if (parent.val < val) {
            parent.right = new TreeNode(val, null, null);
        }else if (parent.val > val) {
            parent.left = new TreeNode(val, null, null);
        }
        return root;
    }
}

// 递归法
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val, null, null);
        }
        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        } else if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        return root;
    }
}

12.二叉搜索树中的删除操作

题目

给定一个二叉搜索树的根结点 root 和一个值 key，删除二叉搜索树中的 key 对应的结点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根结点的引用。

一般来说，删除结点可分为两个步骤：

首先找到需要删除的结点；
如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的结点值是 3，所以我们首先找到 3 这个结点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7],
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

1
2
3

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的结点

示例 3:

1 2	输入: root = [], key = 0 输出: []

提示:

结点数的范围 [0, 104].
-10^5 <= Node.val <= 10^5
结点值唯一
root 是合法的二叉搜索树
-10^5 <= key <= 10^5

思路

递归三部曲：

确定递归函数参数以及返回值：通过递归返回值删除结点。
确定终止条件：遇到空返回，其实这也说明没找到删除的结点，遍历到空结点直接返回了
确定单层递归的逻辑：这里就需要把二叉搜索树中删除结点遇到的情况都搞清楚。有以下五种情况：
- 第一种情况：没找到删除的结点，遍历到空结点直接返回了
- 找到删除的结点
  - 第二种情况：左右孩子都为空（叶子结点），直接删除结点，返回 NULL 为根结点
  - 第三种情况：删除结点的左孩子为空，右孩子不为空，删除结点，右孩子补位，返回右孩子为根结点
  - 第四种情况：删除结点的右孩子为空，左孩子不为空，删除结点，左孩子补位，返回左孩子为根结点
  - 第五种情况：左右孩子结点都不为空，则将删除结点的左子树头结点（左孩子）放到删除结点的右子树的最左面结点的左孩子上，返回删除结点右孩子为新的根结点。
    - 第五种情况有点难以理解，看下面动画：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // 情况1：要删除的结点不存在
        if (root == null) {
            return root;
        }
        if (root.val == key) { // 找到要删除的结点
            // 情况2：要删除的结点为叶子结点
            if (root.left == null && root.right == null) {
                return null;
            }
            // 情况3：要删除的结点的左子树为null
            if (root.left == null) {
                return root.right;
            }
            // 情况4：要删除的结点的右子树为null
            if (root.right == null) {
                return root.left;
            }
            // 情况5：要删除的结点的左右子树都不为null
            if (root.left != null && root.right != null) {
                TreeNode node, parent;
                parent = node = root.right;
                while (node != null) {
                    parent = node;
                    node = node.left;
                }
                parent.left = root.left;
                return root.right;
            }
        } else if (root.val > key){
            root.left = deleteNode(root.left, key);
        } else {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }
}

二叉搜索树删除结点比增加结点复杂的多。因为二叉搜索树添加结点只需要在叶子上添加就可以的，不涉及到结构的调整，而删除结点操作涉及到结构的调整。