简要分析LeetCode树经典题目（Java）

开场白

实战环节

准备工作

遍历问题

LeetCode144. 二叉树的前序遍历

方法一

方法二

LeetCode94. 二叉树的中序遍历

LeetCode145. 二叉树的后序遍历

方法一

方法二

LeetCode102. 二叉树的层序遍历

LeetCode103. 二叉树的锯齿形层序遍历

LeetCode107. 二叉树的层序遍历 II

结构问题

LeetCode104. 二叉树的最大深度

方法一

方法二

LeetCode111. 二叉树的最小深度

方法一

方法二

LeetCode100. 相同的树

方法一

方法二

LeetCode101. 对称二叉树

方法一

方法二

LeetCode226. 翻转二叉树

方法一

方法二

LeetCode199. 二叉树的右视图

N 叉树问题

LeetCode589. N 叉树的前序遍历

方法一递归

方法二迭代

LeetCode590. N 叉树的后序遍历

方法一递归

方法二迭代

LeetCode429. N 叉树的层序遍历

二叉搜索树问题

LeetCode98. 验证二叉搜索树

方法一递归

方法二迭代

LeetCode700. 二叉搜索树中的搜索

LeetCode938. 二叉搜索树的范围和

方法一迭代

方法二深度优先搜索

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

方法一递归

方法二迭代

LeetCode450. 删除二叉搜索树的结点

总结

开场白

在前面几篇文章中，我们简要分析与实现了二叉树与二叉搜索树，本文我们着眼于 $LeetCode$ ，看看基于数据结构树可以引申出哪些有意思的问题。需要提前说明的是，本文中未涉及到使用回溯或动态规划等算法思想的问题，这些遗留的问题将在后续文章中介绍。在本文中涉及到的很多问题同时使用了我们前几篇文章中介绍的栈与队列等数据结构，综合性较强。

在 $Java$ 语言中有一个集合类 $java.util.LinkedList$ ，此集合类实现了队列、双端队列、栈以及链表的常用功能，为了方便，我们在后续题目的代码中将直接使用这个集合类。但是，我们会通过此集合类的变量名来区别其具体使用了哪个集合。

实战环节

准备工作

为了调试方便，我在自定义类 $Solution$ 中根据 $LeetCode$ 中对二叉树结点的定义，创建了内部类 $TreeNode$ 并实现了相应的构造方法。这里为了在后续方法中引用时不产生警告信息，我不再遵循封装思想将其设计为私有化变量。

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

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

        public TreeNode(int val) {
            this.val = val;
        }
    }

遍历问题

对于遍历问题，我们先前在介绍二叉树的文章中已经对其递归实现进行了简要分析，在这里我们主要着眼于这些遍历策略的迭代法实现方式。

LeetCode144. 二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）

本题给定一个二叉树，需要我们返回一个集合，此集合表示对此二叉树进行前序遍历得到的结点元素序列。对于前序遍历，我们可以很容易写出其递归实现的代码，如下。

    public void preOrder(TreeNode root) {
        if (root == null)
            return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

方法一

对于本题，我们只需要将输出结点的语句改成向集合中添加元素操作，即可完成本题的递归实现方案。但需要注意的是，我们应该将结果集合作为函数参数传入到递归函数中，如下。

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

    private void preOrder(TreeNode node, List<Integer> result) {
        if (node == null)
            return;
        result.add(node.val);
        preOrder(node.left, result);
        preOrder(node.right, result);
    }
}

方法二

实际上，二叉树的先序遍历遵循着深度优先搜索（DFS）的思想，我们自然可以使用栈来模拟一系列的递归操作。假设我们使用迭代方式遍历如下图所示的二叉树。

初始状态时，将二叉树的根结点入栈，如下。

在之后的每次操作中，我们需要不断将栈中结点取出，将此结点数据域加入结果集合，然后将此结点的左右孩子按照先右再左的顺序入栈。此时，我们需要取出栈中的栈顶结点 $1$ ，将结点 $1$ 加入到结果集合，此时的结果集合 $result=[1]$ ，随后将 $1$ 的右孩子 $3$ 和左孩子 $2$ 按照给定的顺序入栈，如下。

此时栈顶元素为 $2$ ，将其出栈，将其加入到结果集合，此时的结果集合 $result=[1,2]$ ，随后将此结点的右孩子 $5$ 和左孩子 $4$ 按照给定顺序入栈，如下。

此时栈顶元素为 $4$ ，将其出栈并加入到结果集合，此时的结果集合 $result=[1,2,4]$ ，由于此结点没有左孩子和右孩子，所以不需要做额外的操作，只需要将其出栈即可。出栈后的栈顶元素为 $5$ ，由于此结点与结点 $4$ 相同，没有左右孩子，所以只需要将其加入到结果集合并将其出栈即可，此时的果集合 $result=[1,2,4,5]$ ，如下。

此时栈顶元素为 $3$ ，将其出栈并加入到结果集合，此时的结果集合 $result=[1,2,4,5,3]$ ，随后将此结点的右孩子 $7$ 和左孩子 $6$ 按照给定顺序入栈，如下。

此时栈顶元素为 $6$ ，将其出栈并加入到结果集合，由于此结点没有左孩子和右孩子，于是不再做额外操作。当元素 $6$ 出栈后，此时的栈顶元素为 $7$ ，将其出栈并加入到结果集合，此时的结果集合 $result=[1,2,4,5,3,6,7]$ ，由于此结点没有左孩子和右孩子，于是不需要做额外的操作。

在执行了上述操作后，栈为空，说明对二叉树的前序遍历操作执行完毕，最终的 $result$ 结果集合就是此二叉树的前序遍历结果。可以发现，我们维护的栈的出栈序列就是此二叉树的前序遍历结果，除此之外，栈的另一个作用就是暂存遍历过的结点，因为我们第一次遍历到一个结点时，只是沿着其左孩子指针链向前推进遍历其左子树，而对右子树还没有进行遍历。

通过上述执行流程，我们可以写出迭代法前序遍历代码，如下。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        if (root == null)
            return result;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode popped = stack.pop();
            result.add(popped.val);
            if (popped.right != null)
                stack.push(popped.right);
            if (popped.left != null)
                stack.push(popped.left);
        }
        return result;
    }
}

LeetCode94. 二叉树的中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

通过上一题，相信大家已经明白了在递归函数中如何收集遍历结果，我们在之后的遍历问题中将不再赘述递归实现，而只是给出对应代码。

对于中序遍历的迭代实现方案，我们需要用一个 $TreeNode$ 类型的变量 $temp$ 从根结点开始沿着左孩子指针链向前移动，在必要的时候改变指针链走向，同时依然需要一个栈来暂存先前遍历的结点，一旦 $temp$ 变量为空，就说明此时来到了叶子节点，我们就需要将栈顶元素出栈，并将 $temp$ 指向出栈元素的右孩子。我们依然使用上一题的二叉树模拟一下大致流程。

从根结点开始，我们先让 $temp$ 变量沿着根结点的左孩子指针链前进，直到 $temp=null$ ，并将路途中经过的所有结点入栈，如下。

此时 $temp=null$ ，说明来到了叶子结点，我们不难发现，栈顶元素就是对次二叉树进行中序遍历得到的第一个元素，于是将其出栈并将其加入到结果集合，此时的结果集合 $result=[4]$ 。我们需要根据出栈元素修改变量 $temp$ 使其指向出栈元素的右孩子，修改后我们发现 $temp=null$ ，按照同样的逻辑，我们仍需要出栈一个元素并将其加入到结果集合，此时的结果集合 $result=[4,2]$ ，修改 $temp$ 使其指向出栈元素的右孩子，如下。

此时 $temp$ 不再为 $null$ ，于是沿着当前结点的左孩子指针前进并将当前结点入栈，如下。

由于此结点的左孩子为空，意味着 $temp$ 沿着此结点左指针移动时也为空，于是又要执行出栈操作并改变 $temp$ 。我们将栈顶元素出栈并将其加入到结果集合，此时的结果集合 $result=[4,2,5]$ 。由于结点 $5$ 依然没有右孩子，所以此时的 $temp$ 依旧为空，我们需要继续执行出栈操作，当前栈的状态如下。

此时的栈顶元素为 $1$ ，将栈顶元素出栈并将其加入到结果集合，此时的结果集合 $result=[4,2,5,1]$ ，并将 $temp$ 赋值为出栈元素的左孩子。此时的 $temp$ 变量将继续沿着当前结点的左孩子指针前进，并将沿途结点入栈，如下。

由于结点 $6$ 没有左孩子，故此时有 $temp=null$ ，遂执行出栈操作。我们将结点 $6$ 出栈并加入到结果集合，我们发现结点 $6$ 也没有右孩子，此时 $temp$ 依然为 $null$ ，我们依然执行出栈操作，并将出栈元素加入到结果集合，此时的结果集合 $result=[4,2,5,1,6,3]$ ，由于出栈元素 $3$ 是有右孩子的，所以我们将 $temp$ 赋值为其右孩子，此时栈的状态如下。

此时 $temp$ 不为空，沿着当前结点的左孩子指针前进，并将沿途结点入栈，由于结点 $7$ 没有左孩子，于是执行出栈操作。此时栈中只有元素 $7$ ，于是将其出栈并加入到结果集合，此时的结果集合 $result=[4,2,5,1,6,3,7]$ ，此时出栈元素也没有右孩子，所以 $temp=null$ ，并且此时栈也为空，就说明我们对给定二叉树的中序遍历执行完毕。

通过上述执行流程，我们很容易发现，当 $temp=null$ 且栈为空时，就是整个操作处理完成的标志。栈依然保存着先前已经达到的元素，当一个结点出栈时，就说明其左子树已经遍历完成，如果直接出栈，如何遍历其右子树？此时 $temp$ 变量就派上用场了，当一个结点出栈时就改变 $temp$ 使其指向出栈元素的右孩子，随后执行相同的流程即可。

我们同时可以发现，此问题中栈的出栈序列就是我们对二叉树进行中序遍历得到的序列。虽然未提及递归法的实现，但我们依然给出递归法和迭代法的实现方案，如下。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        // inOrder(root, result);
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode temp = root;
        while (!stack.isEmpty() || temp != null) {
            if (temp != null) {
                stack.push(temp);
                temp = temp.left;
            } else {
                TreeNode popped = stack.pop();
                result.add(popped.val);
                temp = popped.right;
            }
        }
        return result;
    }

    private void inOrder(TreeNode node, List<Integer> result) {
        if (node == null)
            return;
        inOrder(node.left, result);
        result.add(node.val);
        inOrder(node.right, result);
    }
}

LeetCode145. 二叉树的后序遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

方法一

对于此题，我们最先想到的思路是基于前序遍历改编。我们知道，二叉树前序遍历顺序是根—>左—>右，而后序遍历顺序是左—>右—>根，我们不妨通过根—>右—>左的遍历方式遍历二叉树，然后将所得结果集合进行一次反转即可。修改遍历顺序的操作很容易，我们在实现前序遍历的时候，会将每个出栈结点的左右孩子按照先右再左的顺序重新入栈，我们只需要将每个出栈结点的左右孩子按照先左再右的顺序重新入栈即可。我们在此做一解释。由于栈具有先入后出的特性，我们先将出栈结点的右孩子入栈，再将出栈结点的左孩子入栈，每次的出栈元素必然是最后放入的左孩子结点，从宏观上看，就是先处理左子树，反之就是先处理右子树。实现方式如下。需要提前指出的是， $Java$ 中的 $java.util.ArrayList$ 集合继承了 $java.util.Collections$ 集合，而 $java.util.Collections$ 集合中已经定义并实现了集合反转的操作，所以我们只需要直接调用此 $API$ 即可。对于其他面向对象编程语言也可以调用现成的接口方法来实现类似操作，而对于 $C$ 语言则需要我们手写反转集合的操作。

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

方法二

在第二种方法中我们依然使用栈来实现。我们需要定义一个 $TreeNode$ 类型的变量 $pop$ 用来记录上一次出栈的结点，同时需要定义一个 $TreeNode$ 类型的变量 $current$ 从根结点开始沿着左孩子指针链移动，必要时更改方向，除此之外我们依然需要创建一个栈来存储遍历过的元素。我们同样用前文给出的二叉树举例说明。

开始时，我们沿着根结点的左孩子指针链不断向前移动，并将沿途的结点入栈，如下。

此时 $current=null$ ，我们需要执行出栈操作。我们需要将出栈元素加入到结果集合中，此时结果集合 $result=[4]$ ，然后更新表示上一次出栈结点的变量 $pop$ 使其指向出栈的元素 $4$ 。此时我们暂时不需要修改 $current$ ，这是一个与中序遍历不同的地方。

由于此时 $current=null$ ，我们继续执行出栈操作，根据后续遍历规则，我们需要将 $current$ 指向出栈元素的右孩子，并将其入栈，如下。

此时 $current$ 将继续沿着当前结点的左孩子指针向前移动，由于此结点没有左孩子，这导致 $current=null$ ，此时需要将栈顶元素出栈并将其加入到结果集合中，同时修改 $pop$ 变量，此时结果集合 $result=[4,5]$ 。

由于此时 $current$ 依然为空，所以我们继续将栈中结点出栈并将其加入到结果集合中，同时修改 $pop$ 变量，此时结果集合 $result=[4,5,2]$ 。如下。

此时栈顶元素为 $1$ ，根据后序遍历规则，需要将 $current$ 赋值为栈顶元素结点的右孩子。此时 $current$ 将沿着栈顶元素结点的右孩子结点的左孩子指针链向前移动并将沿途结点入栈，如下。

此时 $current=null$ ，我们需要将栈顶元素 $6$ 出栈并将其加入到结果集合中，同时修改 $pop$ 变量，此时结果集合 $result=[4,5,2,6]$ ，如下。

此时 $current$ 依然为空，根据后序遍历规则，我们需要将其更新为新的栈顶元素的右孩子，届时 $current$ 指向的结点将入栈，如下。

此时 $current$ 依然为空，我们需要将栈顶元素出栈并将其加入到结果集合，同时更新 $pop$ 变量，此时结果集合 $result=[4,5,2,6,7]$ ，如下。

此时 $current$ 依然为空，我们需要将栈顶元素出栈并将其加入到结果集合，同时更新 $pop$ 变量，此时结果集合 $result=[4,5,2,6,7,3]$ ，如下。

此时 $current$ 依然为空，我们需要将栈顶元素出栈并将其加入到结果集合，同时更新 $pop$ 变量，此时结果集合 $result=[4,5,2,6,7,3,1]$ ，如下。

最终我们得到的结果集合 $result$ 就是对给定二叉树进行后序遍历的元素序列。

相信细心的读者一定发现了，当 $current=null$ 时我们时而更新 $current$ 为栈顶元素的右孩子，时而对栈顶元素进行结果收集，这两种操作分别对应了什么条件呢？由于后续遍历的特殊性，对于一个结点的右子树，存在两种情况——已访问或未访问，具体来说，我们遍历完一个结点的左子树后需要将此结点的左孩子结点出栈，此时的栈顶元素变成了此结点，这是在出栈阶段我们第一次访问到此结点，此时由于当前结点的右子树还没有遍历，所以我们需要通过此结点的右孩子指针来到此结点的右子树对其进行遍历；当此结点的右子树遍历完成后会将此结点的右孩子结点出栈，此时的栈顶元素又变成了此结点，这是在出栈阶段我们第二次访问到此结点，与第一次不同的是，我们已经完成了对此结点右子树的遍历，此时以此结点为根的子树就遍历完成了，我们需要将此结点从栈中弹出。

问题就转化成，我们如何知道一个结点的右子树已经访问完成呢？这分为两种情况。

如果一个结点的右孩子为空，那么根本不用访问此结点的右子树，换句话说，可以认为此结点的右子树已经访问完成；
如果一个结点的右孩子不为空，那么此结点的右孩子一定是在此之前最后一个出栈的元素，这就是我们单独定义的变量 $pop$ 的意义，如果此结点的右孩子结点恰好与 $pop$ 相等，就说明此结点的右子树已经访问完毕。

理解了思路后，代码实现就很容易了，参考如下。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode current = root;
        TreeNode pop = null;
        while (current != null || !stack.isEmpty()) {
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                    result.add(pop.val);
                } else
                    current = peek.right;
            }
        }
        return result;
    }
}

为了内容完整性，我们依然给出递归实现方式的代码。

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

    private void postOrder(TreeNode node, List<Integer> result) {
        if (node == null)
            return;
        postOrder(node.left, result);
        postOrder(node.right, result);
        result.add(node.val);
    }
}

LeetCode102. 二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

本题给定一个二叉树，需要我们返回一个集合，集合的元素是二叉树每一层的结点集合。换句话说，返回的结果是一个集合的集合，即嵌套集合。

我们前文提到的二叉树的前序遍历遵循着深度优先搜索的思想，本题则遵循着广度优先搜索（BFS）的思想。在实现前序遍历的时候我们使用栈进行模拟，与前者不同的是，我们需要使用队列来模拟实现。

最初，将二叉树的根结点入队，如下。

之后，只要队列不为空，我们就需要做如下的重复操作：每次出队一个结点，如果此结点有左孩子，则将左孩子入队，如果此结点有右孩子，则将右孩子入队。入队的顺序是先左再右。此时，我们将队首元素 $1$ 取出，由于结点 $1$ 既有左孩子也有右孩子，则将左右孩子入队。如下。

此时的队首元素为 $2$ ，将队首结点出队，由于结点 $2$ 既有左孩子也有右孩子，我们将其左右孩子分别入队。如下。

此时的队首元素为 $3$ ，将队首结点出队，由于结点 $3$ 既有左孩子也有右孩子，我们将其左右孩子分别入队。如下。

此时队列中的所有结点都是二叉树中的叶子结点，依次将其出队即可。

通过以上的执行流程我们不难发现，和前几种遍历方式类似的是，出队元素构成的元素序列就是对此二叉树进行层序遍历得到的元素序列。我们根据上述思路，可以写出如下代码。

public class Main {
    public void levelOrder(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode polled = queue.poll();
            System.out.print(polled.val + " ");
            if (polled.left != null)
                queue.offer(polled.left);
            if (polled.right != null)
                queue.offer(polled.right);
        }
    }

    public static void main(String[] args) {
        TreeNode tree = new TreeNode(
                1,
                new TreeNode(
                        2,
                        new TreeNode(4),
                        new TreeNode(5)),
                new TreeNode(
                        3,
                        new TreeNode(6),
                        new TreeNode(7)));
        Solution solution = new Solution();
        solution.levelOrder(tree);
    }
}

经过运行后，我们得到如下结果：

虽然我们成功得到了层序遍历的元素序列，但其层次体现的并不明显，于是我们有如下思路：不妨定义一个变量 $levelNum$ 表示当前层的结点个数，在循环内部定义一个计数器用来统计下一层的结点个数，我们在外层循环的内部再使用一个循环，循环从 $1$ 到 $levelNum$ ，用于从队列中取出指定个数个结点，这些结点就是当前层的结点，对于取出来的每个结点，如果此结点有左孩子，将左孩子入队，如果此结点有右孩子，将右孩子入队，当每个结点入队时都让计数器自增。当内部循环执行完毕后，将计数器的值赋值给 $levelNum$ 。如下。

public class Main {
    public void levelOrder(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int levelNum = 1;
        while (!queue.isEmpty()) {
            int cnt = 0;
            for (int i = 1; i <= levelNum; i ++) {
                TreeNode polled = queue.poll();
                System.out.print(polled.val + " ");
                if (polled.left != null) {
                    queue.offer(polled.left);
                    cnt++;
                }
                if (polled.right != null) {
                    queue.offer(polled.right);
                    cnt++;
                }
            }
            levelNum = cnt;
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(
                1,
                new TreeNode(
                        2,
                        new TreeNode(4),
                        new TreeNode(5)),
                new TreeNode(
                        3,
                        new TreeNode(6),
                        new TreeNode(7)));
        Solution solution = new Solution();
        solution.levelOrder(tree);
    }
}

执行效果如下，可以发现，每一层结束后都会执行换行操作。

在明确了何时换行后，对于本题的解决就容易了。我们只需要把换行操作换成收集每一层的元素操作即可。换句话说，就是在内层循环的外部定义一个集合，当内层循环中每次取出一个结点时，就将其数据域入队，当内层循环结束的时候，将这个集合加入到结果集合中，最终返回结果集合即可。参考实现如下。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null)
            return result;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int levelNum = 1;
        while (!queue.isEmpty()) {
            int cnt = 0;
            List<Integer> level = new ArrayList<>();
            for (int i = 1; i <= levelNum; i++) {
                TreeNode polled = queue.poll();
                level.add(polled.val);
                if (polled.left != null) {
                    queue.offer(polled.left);
                    cnt++;
                }
                if (polled.right != null) {
                    queue.offer(polled.right);
                    cnt++;
                }
            }
            result.add(level);
            levelNum = cnt;
        }
        return result;
    }
}

LeetCode103. 二叉树的锯齿形层序遍历

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

此题给定一个二叉树，要求返回从根结点开始执行锯齿形层序遍历的结果。何为锯齿形层序遍历？我们不妨先将目光回归到层序遍历上，可以看到，对于每一层来说，都是从左到右遍历结点。

而对于锯齿形层序遍历，其大致示意图如下。假设根结点所处的层序号为 $1$ ，不难发现，当层序号为奇数时，遍历方向为从左到右，反之，遍历方向为从右到左。

所以在后续的实现中，我们不妨定义一个 $boolean$ 类型的变量 $odd$ 表示当前层的层序号是否为奇数，初始化为 $true$ 。大体的队列处理流程与上一题的层序遍历是类似的，主要的区别在于结果收集。本题我们将使用一个双端队列来收集结果，当执行出队操作时，我们需要对层序号是否为奇数进行判断，如果为奇数，说明此时按照从左到右的方向遍历的，将出队结点的数据域从队列尾部插入，反之，将出队结点的数据域从队列头部插入，此时的操作相当于向栈中插入元素。每次循环结束的时候，将每层收集的结果加入到结果集合中即可。当内层循环结束后，说明当前层已经处理完毕，即将处理下一层，若当前层的层序号为奇数，那么下一层的层序号则为偶数，反之仍成立，所以在内层循环执行结束后我们还需要将变量 $odd$ 取反。参考实现如下。

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null)
            return result;
        LinkedList<TreeNode> queue = new LinkedList<>();
        boolean odd = true;
        queue.offer(root);
        int levelNum = 1;
        while (!queue.isEmpty()) {
            int cnt = 0;
            LinkedList<Integer> deque = new LinkedList<>();
            for (int i = 1; i <= levelNum; i++) {
                TreeNode polled = queue.poll();
                if (odd)
                    deque.addLast(polled.val);
                else
                    deque.addFirst(polled.val);
                if (polled.left != null) {
                    queue.offer(polled.left);
                    cnt++;
                }
                if (polled.right != null) {
                    queue.offer(polled.right);
                    cnt++;
                }
            }
            odd = !odd;
            levelNum = cnt;
            result.add(deque);
        }
        return result;
    }
}

LeetCode107. 二叉树的层序遍历 II

107. 二叉树的层序遍历 II - 力扣（LeetCode）

与前文分析的层序遍历不同的是，本题需要从最后一层开始收集每一层结点的数据域。唉，我直接调用现成的 $API$ —— $Collections.reverse()$ ，不再赘述，实现代码如下，在原先层序遍历的基础上只增加了一行代码。

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null)
            return result;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int levelNum = 1;
        while (!queue.isEmpty()) {
            int cnt = 0;
            List<Integer> level = new ArrayList<>();
            for (int i = 1; i <= levelNum; i ++) {
                TreeNode polled = queue.poll();
                level.add(polled.val);
                if (polled.left != null) {
                    queue.offer(polled.left);
                    cnt++;
                }
                if (polled.right != null) {
                    queue.offer(polled.right);
                    cnt++;
                }
            }
            levelNum = cnt;
            result.add(level);
        }
        Collections.reverse(result);
        return result;
    }    
}

结构问题

LeetCode104. 二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

本题给定一个二叉树，需要我们返回二叉树的最大深度，二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数，换个角度理解，就是最后一层叶子结点所处的深度。

方法一

最容易想到的方法就是，通过通过层序遍历，找到最大层序号。我们在前文中已经介绍过二叉树的层序遍历方案，需要额外做的操作就是，定义一个计数器，每遍历完一层就让计数器自增。参考实现如下。

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int levelNum = 1, maxDepth = 0;
        while (!queue.isEmpty()) {
            int cnt = 0;
            maxDepth++;
            for (int i = 1; i <= levelNum; i ++) {
                TreeNode polled = queue.poll();
                if (polled.left != null) {
                    queue.offer(polled.left);
                    cnt++;
                }
                if (polled.right != null) {
                    queue.offer(polled.right);
                    cnt++;
                }
            }
            levelNum = cnt;
        }
        return maxDepth;
    }
}

但是从执行效率上看，这种实现方案并不是高效的。

方法二

我们可以基于后序遍历解决此问题，因为每层递归函数执行完毕后恰好可以返回到每棵子树的根结点，对于叶子结点，递归函数执行结束会返回到此结点，只不过此结点没有左右子树而已。实现方案如下。

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

当然，此方仍然可以被简化，如下。

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

我们用下图所示的二叉树来模拟一下函数执行流程。

当传入递归函数的结点不为空时，会不断向递归函数自身传入当前结点的左孩子，只要当前结点的左孩子不为空，将不断执行 int leftDepth = getMaxDepth(root.left)，按照这个流程，将访问到结点 $D$ ，下图中标注颜色的结点表示访问路径上的所有结点。

当来到结点 $D$ 时，将其左孩子（ $null$ ）传入递归函数，由于左孩子为 $null$ ，所以本层将得到 $leftDepth =0$ ，随后将执行 int rightDepth = getMaxDepth(root.right)，将结点 $D$ 的右孩子 $F$ 传入递归函数，由于结点 $F$ 的左孩子为 $null$ ，所以在函数调用栈的 $F$ 层的 $leftDepth =0$ ，随后将结点 $F$ 的右孩子 $G$ 传入递归函数。我们发现结点 $G$ 是二叉树的叶子节点，所以在函数调用栈的 $G$ 层有 $leftDepth = 0$ 且 $rightDepth=0$ ，此时将执行函数的最后一条语句，获取左右子树深度的最大值，并将最大值 $+1$ 后返回到 $G$ 层。如下。

此时来到了函数调用栈的 $F$ 层，这个返回结果将作为 $F$ 层的 $rightDepth$ ，由于当前层有 $leftDepth=0$ ，则函数最后一条语句将返回 $1+1=2$ 给函数调用栈的 $D$ 层。如下。

此时来到了函数调用栈的 $D$ 层，由于当前层有 $leftDepth=0$ ，经过取最大值比较后会将 $2+1=3$ 返回给函数调用栈的 $B$ 层。如下。

此层的返回结果将作为函数调用栈的 $B$ 层的 $leftDepth$ ，在本层中我们只执行了 int leftDepth = getMaxDepth(root.left) 并且我们得到了返回结果 $3$ ，接下来将执行 int rightDepth = getMaxDepth(root.right)，即将结点 $B$ 的右孩子 $E$ 传入递归函数，由于结点 $E$ 为二叉树的叶子结点，按照相同的流程，此递归调用将返回 $1$ 作为结点 $B$ 的 $rightDepth$ 。如下。

对于递归调用层 $B$ 我们已经得到了 $leftDepth$ 及 $rightDepth$ ，经过取最大值并加 $1$ 后得到结果 $3+1=4$ 并将其返回给递归调用层 $A$ 的 $leftDepth$ 。如下。

对于递归调用层 $A$ 我们已经得到了 $leftDepth$ ，此时将结点 $A$ 的右孩子传入递归函数，按照相同的逻辑，得到 $A$ 的 $rightDepth=1$ ，执行函数的最后一条语句得到的结果 $5$ 就是给定二叉树的最大深度。

LeetCode111. 二叉树的最小深度

本题给定一个二叉树，需要我们找出此二叉树的最小深度，最小深度是从根节点到最近叶子节点的最短路径上的节点数量，换个角度理解，就是找到最先出现叶子结点的层序号。

方法一

其实最容易想到的实现方案依然是层序遍历。我们对二叉树进行层序遍历并记录当前层的序号，每遍历完一层后更新层序号变量，不过需要做的额外操作是，当一个结点从队列中出队时，我们需要判断此结点是否为叶子结点。在二叉树中，如果一个结点既没有左孩子，也没有右孩子，就说明此结点是叶子结点。参考实现如下。

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        int levelNum = 1;
        while (!queue.isEmpty()) {
            depth++;
            int cnt = 0;
            for (int i = 1; i <= levelNum; i++) {
                TreeNode polled = queue.poll();
                if (polled.left == null && polled.right == null)
                    return depth;
                if (polled.right != null) {
                    queue.offer(polled.right);
                    cnt++;
                }
                if (polled.left != null) {
                    queue.offer(polled.left);
                    cnt++;
                }
            }
            levelNum = cnt;
        }
        return depth;
    }
}

方法二

实际上我们依然可以遵循后序遍历的特性处理该问题，但是我们需要额外处理一种情况，当一个结点只有左孩子结点时，对于以此结点为根的子树的最小深度是其右子树最小深度加 $1$ ，反之亦然。参考实现如下。

class Solution {
    public int minDepth(TreeNode root) {
        return getMinDepth(root);
    }
    private int getMinDepth(TreeNode node) {
        if (node == null)
            return 0;
        int leftMinDepth = getMinDepth(node.left);
        int rightMinDepth = getMinDepth(node.right);
        if (node.left == null && node.right != null)
            return rightMinDepth + 1;
        if (node.left != null && node.right == null)
            return leftMinDepth + 1;
        return Math.min(leftMinDepth, rightMinDepth) + 1;
    }
}

LeetCode100. 相同的树

本题给定两棵二叉树，我们需要判断这两棵二叉树是否相同，如果两个树在结构上相同，并且结点具有相同的值，则认为二者是相同的。

方法一

实际上，如果两棵树的所有子树是相同的，就可以说明两棵树是相同的。我们可以使用递归的方式实现本题。不妨先考虑清楚最简单结构的判断，具体可以细分为如下三种情况。

如果传入的两个结点都为空，可以说明两棵树是相同的；
如果传入的两个结点只有一个为空，显然这两棵树是不相同的；
如果传入的两个结点都不为空，如果两个结点的数据域不同，则说明两棵树不相同。

对于递归函数的单层处理逻辑，就是判断左右子树是否同时相同。参考实现如下。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return checkIsSame(p, q);
    }
    private boolean checkIsSame(TreeNode p, TreeNode q) {
        if (p == null && q == null)
            return true;
        if (p == null || q == null)
            return false;
        if (p.val != q.val)
            return false;
        return checkIsSame(p.left, q.left) && checkIsSame(p.right, q.right);
    }
}

方法二

我们也可以通过对两棵树同时进行层序遍历进行判断。我们先前介绍过对一棵树进行层序遍历的操作，实际上对两棵树同时进行层序遍历的思路是相似的。我们需要定义两个队列分别保存两棵二叉树的现场情况。

最初先将两棵二叉树的根结点 $p,q$ 分别插入到两个队列 $q1,q2$ 中。当两个队列都不为空时，每次分别从两个队列中取出一个结点，我们记为 $node1,node2$ ，对于出队的两个结点，我们需要对其结构和存储数据进行判断。分为如下两种情况。

二者之一为空，说明结构不同，直接返回 $false$ 即可；
二者不为空，但是存储的数据不同，也意味着二叉树不相同，返回 $false$ 即可。

对于当前结点的判断已经完成了。下面我们需要通过刚才出队的两个结点得到二者的左右孩子，分别为 $left1,left2,right1,right2$ ，我们需要对同侧结点做如下判断。

对于两个左子结点，如果二者之一为空，说明结构不同，直接返回 $false$ 即可；
对于两个右子结点，如果二者之一为空，说明结构不同，直接返回 $false$ 即可。

随后将非空左右子节点分别入队即可。需要指出的是，此时我们不需要对结点的数据域进行判断，因为在每次出队的时候会进行相应判断。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null)
            return true;
        if (p == null || q == null)
            return false;
        LinkedList<TreeNode> q1 = new LinkedList<>();
        LinkedList<TreeNode> q2 = new LinkedList<>();
        q1.offer(p);
        q2.offer(q);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode node1 = q1.poll();
            TreeNode node2 = q2.poll();

            if (node1 == null || node2 == null)
                return false;
            if (node1.val != node2.val)
                return false;

            TreeNode left1 = node1.left;
            TreeNode right1 = node1.right;
            TreeNode left2 = node2.left;
            TreeNode right2 = node2.right;
            
            if (left1 == null && left2 != null)
                return false;
            if (left1 != null && left2 == null)
                return false;
            if (right1 == null && right2 != null)
                return false;
            if (right1 != null && right2 == null)
                return false;
            
            if (left1 != null)
                q1.offer(left1);
            if (right1 != null)
                q1.offer(right1);
            if (left2 != null)
                q2.offer(left2);
            if (right2 != null)
                q2.offer(right2);
        }

        return q1.isEmpty() && q2.isEmpty();
    }
}

不难发现，以上代码的判断条件众多，可以通过异或对布尔表达式进行优化。如下。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null)
            return true;
        if (p == null || q == null)
            return false;
        LinkedList<TreeNode> q1 = new LinkedList<>();
        LinkedList<TreeNode> q2 = new LinkedList<>();
        q1.offer(p);
        q2.offer(q);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode node1 = q1.poll();
            TreeNode node2 = q2.poll();

            if (node1 == null ^ node2 == null)
                return false;
            
            if (node1.val != node2.val)
                return false;

            TreeNode left1 = node1.left;
            TreeNode right1 = node1.right;
            TreeNode left2 = node2.left;
            TreeNode right2 = node2.right;

            if (left1 == null ^ left2 == null)
                return false;
            if (right1 == null ^ right2 == null)
                return false;
            
            if (left1 != null)
                q1.offer(left1);
            if (right1 != null)
                q1.offer(right1);
            if (left2 != null)
                q2.offer(left2);
            if (right2 != null)
                q2.offer(right2);
        }
        return q1.isEmpty() && q2.isEmpty();
    }
}

LeetCode101. 对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

本题给定一个二叉树，判断其是否轴对称。对于以下示意图给出的二叉树，对于第二层的第一个结点来说，其左孩子与第二层第二个结点的右孩子是相同的，其右孩子与第二层第二个结点的左孩子是相同的。用抽象语言归纳就是，假设某层有 $2n$ 个结点，第 $i$ 个结点存储的元素是 $val(i)$ ，若本层结点对称，则有 $val(k)=val(2n-k)$ ，其中 $1\leq k<n$ ，当 $n=1$ 时自然是对称的。

方法一

使用递归方案实现，我们每次向递归函数中传递两个指定位置的结点，在函数内部对两个结点进行对称性的判断。分为如下几种情况。

二者都为空，自然是轴对称的，返回 $true$ ；
二者之一为空，说明在结构上不对称，返回 $false$ ；
二者都不为空，但存储的数据不同，说明在数据存储上不对称，返回 $false$ 。

我们大致描述一下执行流程。对于第一层结点，由于本层只有根结点，自然是对称的。于是我们将根结点的左孩子和右孩子传入递归函数，如下。

对于第二层的结点，数据域是相同的，但不能说明二叉树是轴对称的，我们需要继续递归判断二者的子树是否对称。根据轴对称的特性，对于根结点的左子结点，只有左子结点的左子树与右子结点的右子树轴对称且左子结点的右子树与右子结点的左子树轴对称时，才能说明此二叉树是轴对称的。于是我们先将左子结点的左孩子和右子结点的右孩子传入递归函数。如下。

传入的两个结点的数据域相同，由于两个结点依然有左右子树，所以不能说明此二叉树是轴对称的，需要继续递归判断。于是将第一个结点的左子结点与第二个结点的右子结点传入递归函数，如下。

此时传入的两个结点数据域相同，且其左右孩子指针都为空，那么可以说明第三层第一个结点的左子树与第三层第四个结点的右子树是轴对称的，于是继续判断第三层第一个结点的右子树与第三层第四个结点的左子树是否对称，如下。

此时由于传入的两个结点数据域相同且左右孩子指针都为空，所以说明二者是对称的。进而说明二叉树根结点左子结点的左子树与右子结点的右子树轴对称。此时需要对左子结点的右子树与右子结点的左子树进行判断。按照相同的逻辑，最终可以判断得出整棵二叉树是符合轴对称规则的。参考实现如下。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        return check(root.left, root.right);
    }
    private boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null)
            return true;
        if (left == null)
            return false;
        if (right == null)
            return false;
        if (left.val != right.val)
            return false;
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

方法二

对于本题依然可以使用迭代法实现，我们需要模拟递归函数的执行流程，我们既可以使用栈来模拟，也可以使用队列进行模拟。对于每次的操作，我们只需要保证每次取出的两个结点是处于理想中轴对称位置的结点即可。实现如下。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if (left == null && right == null)
                continue;
            if (left == null)
                return false;
            if (right == null)
                return false;
            if (left.val != right.val)
                return false;
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

LeetCode226. 翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

本题给定一个二叉树，需要翻转这棵二叉树。翻转前后的比较如下。

方法一

若想翻转整棵二叉树，若我们将每个结点的两棵子树进行了翻转，那么整棵树也就翻转成功了，所以最容易想到的就是递归实现思路。我们可以基于二叉树的前序遍历方式执行操作，因为前序遍历是按照根—>左—>右的顺序对二叉树进行遍历的，递归函数中每次传入的结点参数就是根结点或某棵子树的根结点，于是通过这个结点获取到左子结点与右子结点并将二者 $swap$ 即可，随后递归处理此结点的左子树与右子树。参考实现如下。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        invert(root);
        return root;
    }
    private void invert(TreeNode node) {
        if (node == null)
            return;
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        invert(node.left);
        invert(node.right);
    }
}

方法二

由于前序遍历也可以使用栈进行模拟，于是引出了迭代法的实现方案。首先将根结点入栈，在之后的循环处理中，每次从栈中拿到一个结点元素，对其进行翻转，随后将其左孩子与右孩子分别入栈即可，参考实现如下。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode popped = stack.pop();
            TreeNode temp = popped.left;
            popped.left = popped.right;
            popped.right = temp;
            if (popped.left != null)
                stack.push(popped.left);
            if (popped.right != null)
                stack.push(popped.right);
        }
        return root;
    }
}

实际上也可以通过基于后序遍历对二叉树实现翻转操作，不再赘述。

LeetCode199. 二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

本题给定一个二叉树，需要我们返回二叉树的右视图中包含的结点。如下图所示，假设我们站在二叉树的右侧观测二叉树，会看到如下被标记的结点。

最容易想到的方法是层序遍历，每次得到层的最后一个结点即可。在函数的实现中，需要定义一个表示当前层结点数的变量 $levelNum$ ，当队列不为空时执行 $levelNum$ 次出队操作，在此循环外需要定义一个计数器用于表示当前层的下一层具有的结点数量，在后续对每个结点进行处理时不断更新计数器，最终将计数器的值赋值给 $levelNum$ 即可。在循环内部，当循环下标与 $levelNum$ 相同时就说明当前出队结点就是当前层的最后一个结点。参考实现如下。

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

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int levelNum = 1;

        while (!queue.isEmpty()) {
            int cnt = 0;
            for (int i = 1; i <= levelNum; i++) {
                TreeNode polled = queue.poll();
                if (i == levelNum)
                    result.add(polled.val);
                if (polled.left != null) {
                    queue.offer(polled.left);
                    cnt++;
                }
                if (polled.right != null) {
                    queue.offer(polled.right);
                    cnt++;
                }
            }
            levelNum = cnt;
        }
        return result;
    }
}

N 叉树问题

二叉树在实现一些功能上具有局限性，因为每个结点只有两个子结点，于是我们引出了N叉树。与二叉树不同的是， $N$ 叉树的每个结点可以有多个子结点，我们可以用一个数组或集合存储每个结点的子结点，经典高级数据结构字典树就可以使用 $N$ 叉树实现。 $LeetCode$ 对 $N$ 叉树的结点定义如下。

public class Node {
    public int val;
    public List<Solution.Node> children;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Solution.Node> _children) {
        val = _val;
        children = _children;
    }
}

接下来我们来看看，在遍历问题上，如何从二叉树推广到 $N$ 叉树

LeetCode589. N 叉树的前序遍历

589. N 叉树的前序遍历 - 力扣（LeetCode）

我们在前文提到过，二叉树的前序遍历实际上遵循了深度优先搜索的思想，与正统 $DFS$ 不同的是，对二叉树进行深搜只是分别对每个结点的两个孩子进行深搜，所以推广到 $N$ 叉树，我们需要对每个结点的所有孩子进行深搜的递归调用。参考实现如下。

方法一递归

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null)
            return result;
        result.add(root.val);
        doPreOrder(root, result);
        return result;
    }
    private void doPreOrder(Node node, List<Integer> result) {
        if (node == null)
            return;
        for (Node child : node.children) {
            result.add(child.val);
            doPreOrder(child, result);
        }
    }
}

方法二迭代

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null)
            return result;
        LinkedList<Node> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node popped = stack.pop();
            result.add(popped.val);
            for (int i = popped.children.size() - 1; i >= 0; i--)
                stack.push(popped.children.get(i));
        }
        return result;
    }
}

LeetCode590. N 叉树的后序遍历

590. N 叉树的后序遍历 - 力扣（LeetCode）

参考上一题的实现，这里直接给出对应实现代码。

方法一递归

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null)
            return result;
        doPostOrder(root, result);
        result.add(root.val);
        return result;
    }
    private void doPostOrder(Node node, List<Integer> result) {
        if (node == null)
            return;
        for (Node child : node.children) {
            doPostOrder(child, result);
            result.add(child.val);
        }
    }
}

方法二迭代

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null)
            return result;
        LinkedList<Node> stack = new LinkedList<>();
        Node pop = null;
        stack.push(root);
        while (!stack.isEmpty()) {
            Node popped = stack.pop();
            for (Node child : popped.children)
                stack.push(child);
            result.add(popped.val);
        }
        Collections.reverse(result);
        return result;
    }
}

LeetCode429. N 叉树的层序遍历

429. N 叉树的层序遍历 - 力扣（LeetCode）

与二叉树层序遍历不同的是，在 $N$ 叉树的层序遍历中需要将每次出队元素的所有孩子入队，其他部分与二叉树层序遍历实现思路一致，不再赘述。参考实现如下。

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new LinkedList<>();
        if (root == null)
            return result;
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        int levelNum = 1;
        while (!queue.isEmpty()) {
            List<Integer> level = new LinkedList<>();
            int cnt = 0;
            for (int i = 1; i <= levelNum; i ++) {
                Node polled = queue.poll();
                level.add(polled.val);
                for (Node child : polled.children) {
                    queue.offer(child);
                    cnt++;
                }
            }
            levelNum = cnt;
            result.add(level);
        }
        return result;
    }
}

二叉搜索树问题

LeetCode98. 验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）

本题给定一个二叉树，判断其是否是一个二叉搜索树。在之前的文章中我们对二叉树做了简要分析与实现，我们知道二叉搜索树是具有如下性质的二叉树。

结点的左子树存储的元素均小于此结点存储的元素；
结点的右子树存储的元素均大于此结点存储的元素；
结点的左右子树也是一棵二叉搜索树。

同时根据二叉搜索树特性我们发现，对一棵二叉搜索树进行中序遍历得到的元素序列是严格单调递增的。根据这个特性，我们就很容易完成本题的实现。

方法一递归

我们可以基于中序遍历修改操作逻辑完成本题。对于边界情况，如果传入的结点为空，可以返回 $true$ ，因为可以认为空树是一棵二叉搜索树。对于当前结点，递归调用判断其左子树和右子树分别是否为二叉搜索树。参考实现如下。

class Solution {
    private long previous = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        boolean a = isValidBST(root.left);
        if (!a)
            return false;
        if (previous >= root.val)
            return false;
        previous = root.val;
        return isValidBST(root.right);
    }
}

方法二迭代

对于迭代实现，先对特殊情况进行判断。如果传入的根结点为空，可以认为其是一棵二叉搜索树；如果根结点既没有左孩子也没有右孩子，那么自然这棵树也是二叉搜索树。之后就是执行用栈模拟中序遍历操作了，不过在遍历的时候需要将当前出栈的元素与上一次出栈的元素的数据域进行比较，我们需要定义一个变量保存上一次出栈元素的数据域。参考实现如下。

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        if (root.left == null && root.right == null)
            return true;

        long compare = Long.MIN_VALUE;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode temp = root;
        while (temp != null || !stack.isEmpty()) {
            if (temp != null) {
                stack.push(temp);
                temp = temp.left;
            } else {
                TreeNode popped = stack.pop();
                if (popped.val <= compare)
                    return false;
                compare = (long) popped.val;
                temp = popped.right;
            }
        }
        return true;
    }
}

LeetCode700. 二叉搜索树中的搜索

700. 二叉搜索树中的搜索 - 力扣（LeetCode）

本题给定一个二叉树和一个整型变量，需要在二叉搜索树中查找到存储着此数据的结点并返回。若不存在这样的结点则返回 $null$ 。

根据二叉搜索树的定义，对于每个结点来说，其左子树存储的数据均小于此结点存储的数据；其右子树存储的数据均大于此结点存储的数据。所以在查找过程中，先对根结点进行查询，如果给定值小于根结点存储值，则沿着根结点左孩子指针在其左子树中查找，反之在其右子树中查找，对于每个结点执行相同的逻辑。如果查找到叶子结点都没有发现满足条件的结点，则说明整棵树中不存在存储给定值的结点，返回 $null$ 即可。

由于本题的递归实现与迭代实现思路是相同的，我们直接给出更加高效的迭代实现方案。参考如下。

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

LeetCode938. 二叉搜索树的范围和

938. 二叉搜索树的范围和 - 力扣（LeetCode）

本题给定一个二叉树和一个数据域范围 $[low, high]$ ，需要在二叉树中找到结点存储数据在此范围内的所有数据并求和返回。在之前的文章中我们介绍过查找小于给定值和大于给定值的数据集合，根据二叉搜索树的定义，对于前者可以通过中序遍历，如果当前结点的数据域已经超过给定值，意味着之后的所有元素都会超过给定值，则不需要再进行后续的遍历，直接返回结果集合即可；对于后者可以通过反向中序遍历，如果当前结点的数据域小于给定值，说明在后续遍历中得到的结点存储的数据均小于给定值，则不需要进行后续的遍历，直接返回结果集合即可。

对于这两个需求，我们可以找到合适的时机结束操作而避免无效的遍历，但对于范围和，这种时机是不容易找到的，因为范围区间可能处于结点存储元素集合的中间区域，不论采取正向中序遍历还是反向中序遍历，都会存在无效的元素。参考实现如下

方法一迭代

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode temp = root;
        while (temp != null || !stack.isEmpty()) {
            if (temp != null) {
                stack.push(temp);
                temp = temp.left;
            } else {
                TreeNode popped = stack.pop();
                if (low <= popped.val && popped.val <= high)
                    sum += popped.val;
                if (popped.val > high)
                    break;
                temp = popped.right;
            }
        }
        return sum;
    }
}

方法二深度优先搜索

上面提供的方法的执行效率并不算高，我们可以基于深度优先搜索的思想解决问题。参考实现如下。

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null)
            return 0;
        if (root.val > high)
            return rangeSumBST(root.left, low, high);
        if (low > root.val)
            return rangeSumBST(root.right, low, high);
        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }
}

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

701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

本题给定一个二叉搜索树和一个指定值 $val$ ，需要将 $val$ 插入到二叉搜索树中。这需要我们根据二叉搜索树的特点找到合适的位置插入。我们采取二分策略，先对根结点进行判断，如果 $val$ 大于根结点存储的值，则在根结点右子树中寻找插入位置；反之在跟系欸但左子树中寻找插入位置，对所有结点都执行相同的操作，直到用于遍历的结点为空为止。我们需要定义一个结点变量用于保存当前遍历结点的父结点 $parent$ ，如果遍历结点为 $null$ ，说明 $parent$ 处于二叉搜索树的叶子结点。此时就需要执行插入操作了，如果 $val$ 大于 $parent$ 存储的数据，则将数据域为 $val$ 的结点作为 $parent$ 的右孩子存储；反之作为 $parent$ 的左孩子存储。参考实现如下。

方法一递归

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null)
            return new TreeNode(val);
        insertNode(root, val);
        return root;
    }
    public TreeNode insertNode(TreeNode node, int val) {
        if (node == null)
            return new TreeNode(val);
        if (node.val < val)
            node.right = insertNode(node.right, val);
        else 
            node.left = insertNode(node.left, val);
        return node;
    }
}

方法二迭代

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null)
            return new TreeNode(val);
        TreeNode temp = root;
        TreeNode parent = null;
        while (temp != null) {
            parent = temp;
            if (temp.val < val)
                temp = temp.right;
            else 
                temp = temp.left;
        }
        
        if (parent.val < val)
            parent.right = new TreeNode(val);
        else 
            parent.left = new TreeNode(val);
        return root;
    }
}

LeetCode450. 删除二叉搜索树的结点

450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

本题给定一个二叉搜索树和一个指定值 $key$ ，需要将二叉搜索树中值为 $key$ 的结点删除。对于二叉搜索树中的删除操作，我们需要根据二叉搜索树特点找到此结点，然后找到此结点的后任，届时此结点的后任将作为一个存储与此结点位置的新结点，在移动结点之前需要处理后任结点的后事，即将后任结点的右孩子托孤给后任的父结点，后任结点的左孩子呢？实际上如果确定此结点为待删除结点的后任，那么此结点一定没有左孩子，否则此结点的左孩子将是待删除结点的后任，换句话说，当前结点是待删除结点的后任与当前结点有左孩子是互斥的。参考实现如下。

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return root;
        if (root.val == key) {
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;
            else {
                TreeNode successor = root.right;
                while (successor.left != null)
                    successor = successor.left;
                successor.left = root.left;
                root = root.right;
            }
        }
        if (root.val < key)
            root.right = deleteNode(root.right, key);
        if (key < root.val)
            root.left = deleteNode(root.left, key);
        return root;
    }
}