CS Manual

Appearance

树 ​

从根到叶的通过参数传递, 从叶到根通过 res 传递。

借助栈可以实现任意顺序迭代遍历, 后序麻烦一点

  • 左-根-右，顺序: 根入栈, 左入栈, 出栈(visit), 右入栈
  • 根-左-右，顺序: 根入栈, 出栈(visit), 右入栈, 左入栈
  • 左-右-根，顺序: 根入栈, 左入栈, peek, 右子树未处理则右入栈, 处理过则出栈

从根到叶 ​

94. 二叉树的中序遍历 easy ​

给定一个二叉树的根节点 root, 返回 它的 中序 遍历。

解法 1 递归

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

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

解法 2 栈

栈可以通过入栈顺序任意实现遍历顺序
左-根-右, 顺序: 根入栈, 左入栈, 出栈(visit), 右入栈

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

解法 3 Morris

98. 验证二叉搜索树 mid ​

给你一个二叉树的根节点 root, 判断其是否是一个有效的二叉搜索树。

全树节点在 [min,max] 范围内
也可以通过中序遍历判断

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

    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        //左子树范围[minval, val]
        //右子数范围[val, maxval]
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}

101. 对称二叉树 easy ​

剑指 Offer 28. 对称的二叉树

给你一个二叉树的根节点 root, 检查它是否轴对称。

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

    public boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

112. 路径总和 easy ​

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。判断该树中是否存在 根节点到叶子节点 的路径, 这条路径上所有节点值相加等于目标和 targetSum。如果存在, 返回 true；否则, 返回 false。

叶子节点 是指没有子节点的节点。

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

129. 求根节点到叶节点数字之和 mid ​

LCR 049. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root, 树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字：

例如, 从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123。 计算从根节点到叶节点生成的 所有数字之和。

从根到叶的通过参数传递, 从叶到根通过 res 传递

java
class Solution {

    public int sumNumbers(TreeNode root) {
        return sum(0, root);
    }

    int sum(int pre, TreeNode node) {
        if (node == null) return 0;
        pre *= 10;
        pre += node.val;
        if (node.left == null && node.right == null) return pre;
        return sum(pre, node.left) + sum(pre, node.right);
    }
}

144. 二叉树的前序遍历 easy ​

给你二叉树的根节点 root, 返回它节点值的 前序 遍历。

解法 1 递归

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

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

解法 2 迭代

根-左-右 顺序为: 根入栈, 出栈(visit), 右入栈, 左入栈

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

145. 二叉树的后序遍历 easy ​

给你一棵二叉树的根节点 root, 返回其节点值的 后序遍历。

解法 1 递归

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

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

解法 2 迭代

左-右-根, 顺序: 根入栈, 左入栈, peek, 右子树未处理则右入栈, 处理过则出栈
根节点的前一个节点应该是右子树的根节点

java
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
                continue;
            }
            root = stack.element();
            if (root.right == null || root.right == pre) {
                res.add(root.val);
                pre = root;
                stack.pop();
            } else root = root.right;
        }
        return res;
    }
}

找值 ​

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

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。

更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。

给出这样的一个二叉树，你需要输出所有节点中的 第二小的值。

如果第二小的值不存在的话，输出 -1。

dfs 暴力搜

java
class Solution {
    int min;
    int res = -1;

    public int findSecondMinimumValue(TreeNode root) {
        min = root.val;
        dfs(root);
        return res;
    }

    private void dfs(TreeNode node) {
        if (node == null) return;
        if (min == node.val) {
            dfs(node.left);
            dfs(node.right);
        } else if (res == -1 || node.val < res) {
            res = node.val;
        }
    }
}

从叶到根 ​

104. 二叉树的最大深度 easy ​

剑指 Offer 55 - I. 二叉树的深度

给定一个二叉树, 找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

可以 BFS, 但递归更简单

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

110. 平衡二叉树 easy ​

剑指 Offer 55 - II. 平衡二叉树

给定一个二叉树, 判断它是否是高度平衡的二叉树。

本题中, 一棵高度平衡二叉树定义为：

  • 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

解法 自底向上

要将底部的结果透出给到顶部, 还要返回树的高度

java
class Solution {
    public boolean isBalanced(TreeNode root) {
        return deep(root) != -1;
    }

    private int deep(TreeNode node) {
        if (node == null) return 0;
        int left = deep(node.left);
        int right = deep(node.right);
        if (left == -1 || right == -1
                || Math.abs(left - right) > 1) return -1;
        return 1 + Math.max(left, right);
    }
}

111. 二叉树的最小深度 easy ​

给定一个二叉树, 找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

解法 1: DFS

注意, 有子节点的不是叶子节点

java
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int l = minDepth(root.left);
        int r = minDepth(root.right);
        if (l == 0 || r == 0) return l + r + 1; // 单子树
        return Math.min(l, r) + 1;
    }
}

解法 2: BFS

java
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        int cnt = 1;
        while (que.size() > 0) {
            int size = que.size();
            while (size-- > 0) {
                TreeNode node = que.remove();
                if (node.left == null && node.right == null) return cnt;
                if (node.left != null) que.add(node.left);
                if (node.right != null) que.add(node.right);
            }
            cnt++;
        }
        return cnt;
    }
}

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

LCR 051. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给定一个二叉树的根节点 root，返回其 最大路径和，即所有路径上节点值之和的最大值。

全局 max 从每个子树得到

java
class Solution {
    int max;
    public int maxPathSum(TreeNode root) {
        max = root.val;
        deep(root);
        return max;
    }
    private int deep(TreeNode root) {
        if (root == null)  return 0;
        int left = Math.max(0, deep(root.left));
        int right = Math.max(0, deep(root.right));
        max = Math.max(max, root.val + left + right);
        return root.val + Math.max(left, right);
    }
}

404. 左叶子之和 easy ​

给定二叉树的根节点 root, 返回所有左叶子之和。

解法 1 DFS

java
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return sumOfLeftLeaves(root.left, true) + sumOfLeftLeaves(root.right, false);
    }

    public int sumOfLeftLeaves(TreeNode root, boolean isLeft) {
        if (root == null) return 0;
        if (isLeft && root.left == null && root.right == null) return root.val;
        return sumOfLeftLeaves(root.left, true) + sumOfLeftLeaves(root.right, false);
    }
}

解法 2 BFS

略

543. 二叉树的直径 easy ​

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

解法

维护全局 max, 遍历每个 node, 函数返回最大深度

java
class Solution {
    int max = 0;

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

    private int deep(TreeNode node) {
        if (node == null) return 0;
        int left = deep(node.left);
        int right = deep(node.right);
        int len = left + right;
        max = Math.max(max, len);
        return 1 + Math.max(left, right);
    }
}

590. N 叉树的后序遍历 easy ​

给定一个 n 叉树的根节点 root，返回 其节点值的 后序遍历。

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

java
class Solution {

    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    public void postorder(Node root, List<Integer> res) {
        if (root == null) return;
        for (Node n : root.children) {
            postorder(n, res);
        }
        res.add(root.val);
    }
}

687. 最长同值路径 mid ​

给定一个二叉树的 root，返回 最长的路径的长度，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

两个节点之间的路径长度 由它们之间的边数表示。

从叶到根

每个节点作为 root 求得全局最大值, 递归函数返回最长单边

java
class Solution {
    int res;

    public int longestUnivaluePath(TreeNode root) {
        help(root);
        return res;
    }

    public int help(TreeNode node) {
        if (node == null) return 0;
        int l = 0, r = 0;
        int left = help(node.left);
        int right = help(node.right);
        if (node.left != null && node.left.val == node.val) l = left + 1;
        if (node.right != null && node.right.val == node.val) r = right + 1;
        res = Math.max(res, l + r);
        return Math.max(l, r);
    }
}

814. 二叉树剪枝 mid ​

LCR 047. 二叉树剪枝

给你二叉树的根结点 root，此外树的每个结点的值要么是 0，要么是 1。

返回移除了所有不包含 1 的子树的原二叉树。

节点 node 的子树为 node 本身加上所有 node 的后代。

自底向上

java
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0) return null;
        else return root;
    }
}

构造 ​

105. 从前序与中序遍历序列构造二叉树 mid ​

剑指 Offer 07. 重建二叉树

给定两个整数数组 preorder 和 inorder, 其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历, 请构造二叉树并返回其根节点。

  • 均 无重复 元素

解法 1 递归

前序可以将中序二分, 不断将中序二分建树

java
class Solution {

    // 前序的索引, 需要共享
    int p = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 中序的反向索引
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(map, preorder, inorder, 0, inorder.length - 1);
    }

    // l, r: 中序的索引
    private TreeNode build(Map<Integer, Integer> map, int[] preorder, int[] inorder, int l, int r) {
        if (l > r) return null;
        int val = preorder[p++];
        // i: 中序的idx
        int i = map.get(val);
        // 下面的构造顺序要跟 pre 保持一致
        TreeNode root = new TreeNode(val);
        if (l == r) return root;
        root.left  = build(map, preorder, inorder, l, i - 1);
        root.right = build(map, preorder, inorder, i + 1, r);
        return root;
    }
}

解法 2 迭代

114. 二叉树展开为链表 mid ​

给你二叉树的根结点 root, 请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode, 其中 right 子指针指向链表中下一个结点, 而左子指针始终为 null。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

解法 前序遍历, 把右子树接在左子树最右

前序遍历; 右子树存下来, 左子树变为右子树, 左子树置空, 找到右(之前的左)子树的最右节点, 把之前的右子树接上

java
class Solution {
    public void flatten(TreeNode root) {
        while (root != null) {
            TreeNode l = root.left;
            TreeNode r = root.right;
            root.left = null;
            root.right = l;
            TreeNode pre = root;
            while (pre.right != null) pre = pre.right;
            pre.right = r;
            root = root.right;
        }
    }
}

297. 二叉树的序列化与反序列化 hard ​

LCR 048. 二叉树的序列化与反序列化

序列化的顺序跟反序列化的顺序要一致

解法 1 层序

层序的叶子结点都用'X'做了封底, 下一层的数量是上层的 2 倍, 只要按序出队, 接在上层即可

java
class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            TreeNode node = que.remove();
            if (node == null) sb.append("X,");
            else {
                sb.append(node.val).append(",");
                que.add(node.left);
                que.add(node.right);
            }
        }
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if ("".equals(data)) return null;
        Queue<String> nodes = new ArrayDeque<>(List.of(data.split(",")));
        TreeNode root = new TreeNode(Integer.parseInt(nodes.remove()));
        Queue<TreeNode> que = new ArrayDeque<>();
        que.add(root);
        while (!que.isEmpty()) {
            TreeNode parent = que.remove();
            String left = nodes.remove();
            String right = nodes.remove();
            if (!left.equals("X")) {
                TreeNode l = new TreeNode(Integer.parseInt(left));
                parent.left = l;
                que.add(l);
            }
            if (!right.equals("X")) {
                TreeNode r = new TreeNode(Integer.parseInt(right));
                parent.right = r;
                que.add(r);
            }
        }
        return root;
    }
}

解法 2 前序

递归, 更简洁, 只要找到封底就 return

java
class Codec {

    public String serialize(TreeNode root) {
        if (root == null) return "X,";
        String left = serialize(root.left);
        String right = serialize(root.right);
        return root.val + "," + left + right;
    }

    public TreeNode deserialize(String data) {
        Queue<String> queue = new ArrayDeque<>(List.of(data.split(",")));
        return buildTree(queue);
    }

    private TreeNode buildTree(Queue<String> queue) {
        String val = queue.remove();
        if ("X".equals(val)) return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = buildTree(queue);
        node.right = buildTree(queue);
        return node;
    }
}

617. 合并二叉树 easy ​

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

java
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}

897. 递增顺序搜索树 easy ​

LCR 052. 递增顺序搜索树

给你一棵二叉搜索树的 root，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

中序遍历的过程中记一下前一个节点即可

java
class Solution {
    private TreeNode pre;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode zero = new TreeNode();
        pre = zero;
        midTraverse(root);
        return zero.right;
    }

    private void midTraverse(TreeNode node) {
        if (node == null) return;
        midTraverse(node.left);
        pre.right = node;
        node.left = null;
        pre = node;
        midTraverse(node.right);
    }
}

919. 完全二叉树插入器 mid ​

LCR 043. 完全二叉树插入器

完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。

设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。

实现 CBTInserter 类:

  • CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
  • CBTInserter.insert(int v) 向树中插入一个值为 Node.val == val 的新节点 TreeNode。使树保持完全二叉树的状态，并返回插入节点 TreeNode 的父节点的值；
  • CBTInserter.get_root() 将返回树的头节点。
java
class CBTInserter {

    Queue<TreeNode> notFull = new LinkedList<>();
    TreeNode root;

    public CBTInserter(TreeNode root) {
        this.root = root;
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            TreeNode node = que.remove();
            if (node.left != null) que.add(node.left);
            if (node.right != null) que.add(node.right);
            if (node.left == null || node.right == null) notFull.add(node);
        }
    }

    public int insert(int v) {
        TreeNode parent = notFull.remove();
        TreeNode child = new TreeNode(v);
        if (parent.left == null)
            parent.left = child;
        else
            parent.right = child;
        notFull.add(child);
        return parent.val;
    }

    public TreeNode get_root() {
        return root;
    }
}

构造 BST ​

108. 从有序数组中构造二叉查找树 easy ​

给你一个整数数组 nums, 其中元素已经按 升序 排列, 请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足 "每个节点的左右两个子树的高度差的绝对值不超过 1" 的二叉树。

中序遍历, 输入数组范围, 递归左右子树, 返回根节点

java
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    private TreeNode sortedArrayToBST(int[] nums, int l, int h) {
        if (l > h) return null;
        int m = l + (h - l >> 1);
        TreeNode node = new TreeNode(nums[m]);
        node.left = sortedArrayToBST(nums, l, m - 1);
        node.right = sortedArrayToBST(nums, m + 1, h);
        return node;
    }
}

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

给定一个单链表的头节点 head, 其中的元素按升序排序, 将其转换为高度平衡的二叉搜索树。

本题中, 一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

解法一: 前序构造, 寻找中节点

求中点时, 一个前闭后开的区间[)方便处理, 那 right 要偏向右侧 复杂度在寻找中间节点 可以用数组维护中间节点优化

java
public class Solution {

    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode left, ListNode right) {
        // 前闭后开
        if (left == right) return null;
        // 中点偏右
        ListNode mid = this.getMedian(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left, mid);
        root.right = buildTree(mid.next, right);
        return root;
    }

    // 快慢指针
    public ListNode getMedian(ListNode left, ListNode right) {
        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next != right) {
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

解法二: 中序构造

中序遍历就是链表的顺序, 掌控好二分出来的数量

java
class Solution {
    ListNode globalHead;

    public TreeNode sortedListToBST(ListNode head) {
        globalHead = head;
        int length = getLength(head);
        return buildTree(0, length - 1);
    }

    public int getLength(ListNode node) {
        int ret = 0;
        while (node != null) {
            ++ret;
            node = node.next;
        }
        return ret;
    }

    // l,r 在这可以理解为索引, 实际上是数量
    public TreeNode buildTree(int left, int right) {
        if (left > right) return null;
        int mid = left + right >> 1;
        TreeNode root = new TreeNode();
        root.left = buildTree(left, mid - 1);
        root.val = globalHead.val;
        globalHead = globalHead.next;
        root.right = buildTree(mid + 1, right);
        return root;
    }
}

层序遍历 ​

102. 二叉树的层序遍历 mid ​

剑指 Offer 32 - I. 从上到下打印二叉树 剑指 Offer 32 - II. 从上到下打印二叉树 II

给你二叉树的根节点 root, 返回其节点值的 层序遍历

java
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            int size = que.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode node = que.remove();
                list.add(node.val);
                if (node.left != null) que.add(node.left);
                if (node.right != null) que.add(node.right);
            }
            res.add(list);
        }
        return res;
    }
}

103. 二叉树的锯齿形层序遍历 mid ​

给你二叉树的根节点 root, 返回其节点值的 锯齿形层序遍历 。（即先从左往右, 再从右往左进行下一层遍历, 以此类推, 层与层之间交替进行）。

java
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) return List.of();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        List<List<Integer>> res = new ArrayList<>();
        boolean left = true;
        while (!que.isEmpty()) {
            int size = que.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode node = que.remove();
                list.add(node.val);
                if (node.left != null) que.add(node.left);
                if (node.right != null) que.add(node.right);
            }
            res.add(list);
            if (!left) Collections.reverse(list);
            left ^= true;
        }
        return res;
    }
}

116. 填充每个节点的下一个右侧节点指针 mid ​

给定一个 完美二叉树, 其所有叶子节点都在同一层, 每个父节点都有两个子节点。二叉树定义如下：

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

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

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

解法 1 BFS

java
class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                Node node = que.remove();
                if (node.left != null) que.add(node.left);
                if (node.right != null) que.add(node.right);
                if (size > 0) node.next = que.element();
            }
        }
        return root;
    }
}

解法 2 利用上一层的横向指针

在同一行中, 相邻两个元素有可能属于同一父节点, 有可能属于不同但相邻的父节点
在完美二叉树里可行, 如果不满就不可行

java
class Solution {
    public Node connect(Node root) {
        if (root == null) return root;
        Node first = root;
        // 处理下一层
        while (first.left != null) {
            Node head = first;
            while (head != null) {
                head.left.next = head.right;
                if (head.next != null)
                    head.right.next = head.next.left;
                head = head.next;
            }
            first = first.left;
        }
        return root;
    }
}

199. 二叉树的右视图 mid ​

LCR 046. 二叉树的右视图

给定一个二叉树的 根节点 root, 想象自己站在它的右侧, 按照从顶部到底部的顺序, 返回从右侧所能看到的节点值。

解法 1 BFS

第 1 反应 BFS

java
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            int size = que.size();
            TreeNode node;
            while (size-- > 0) {
                node = que.remove();
                if (node.left != null) que.add(node.left);
                if (node.right != null) que.add(node.right);
            }
            res.add(node.val); // 用最后1个
        }
        return res;
    }
}

解法 2 DFS

也可以 DFS, 只要知道遍历过程中的深度

java
class Solution {
    List<Integer> res;

    public List<Integer> rightSideView(TreeNode root) {
        res = new ArrayList<>();
        dfs(root, 0);
        return res;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) return;
        if (res.size() <= depth) res.add(node.val);
        dfs(node.right, depth + 1);
        dfs(node.left, depth + 1);
    }
}

513. 找树左下角的值 mid ​

LCR 045. 找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

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

515. 在每个树行中找最大值 mid ​

LCR 044. 在每个树行中找最大值

给定一棵二叉树的根节点 root，请找出该二叉树中每一层的最大值。

java
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            int size = que.size();
            int max = Integer.MIN_VALUE;
            while (size-- > 0) {
                TreeNode node = que.remove();
                max = Math.max(max, node.val);
                if (node.left != null) que.add(node.left);
                if (node.right != null) que.add(node.right);
            }
            list.add(max);
        }
        return list;
    }
}

637. 二叉树的层平均值 easy ​

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

java
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            int size = que.size();
            double sum = 0;
            int cnt = 0;
            while (size-- > 0) {
                TreeNode node = que.remove();
                sum += node.val;
                cnt++;
                if (node.left != null) que.add(node.left);
                if (node.right != null) que.add(node.right);
            }
            res.add(sum / cnt);
        }
        return res;
    }
}

662. 二叉树最大宽度 ​

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

解法 1 BFS

java
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Queue<TreeNode> q1 = new ArrayDeque<>();
        q1.add(root);
        Queue<Integer> q2 = new ArrayDeque<>();
        q2.add(0);
        int res = 0;
        while (!q1.isEmpty()) {
            int size = q1.size();
            TreeNode ln = null, rn = null;
            Integer li = null, ri = null;
            while (size-- > 0) {
                rn = q1.remove();
                if (ln == null) ln = rn;
                ri = q2.remove();
                if (li == null) li = ri;

                if (rn.left != null) {
                    q1.add(rn.left);
                    q2.add(ri * 2);
                }
                if (rn.right != null) {
                    q1.add(rn.right);
                    q2.add(ri * 2 + 1);
                }
            }
            res = Math.max(res, ri - li + 1);
        }
        return res;
    }
}

解法 2 DFS

先左后右, 用 map 存, 到右边的时候计算即可

java
class Solution {
    Map<Integer, Integer> map = new HashMap<>();

    public int widthOfBinaryTree(TreeNode root) {
        return dfs(root, 1, 1);
    }

    public int dfs(TreeNode node, int depth, int idx) {
        if (node == null) return 0;
        map.putIfAbsent(depth, idx);
        return Math.max(
                idx - map.get(depth) + 1,
                Math.max(
                        dfs(node.left, depth + 1, idx * 2),
                        dfs(node.right, depth + 1, idx * 2 + 1)
                )
        );
    }
}

枚举所有树 ​

分治左右两边

95. 不同的二叉搜索树 II mid ​

给你一个整数 n, 请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树。可以按 任意顺序 返回答案。

根节点 i 从 1==>n, 左右子树递归返回树根节点列表, 互相匹配

Java
class Solution {
    public List<TreeNode> generateTrees(int n) {
        // 根节点确定后 左右子树的集合确定
        return generateTrees(1, n);
    }

    /**
     * 输入左右边界, 返回根节点列表
     */
    public List<TreeNode> generateTrees(int l, int r) {
        List<TreeNode> res = new ArrayList<>();
        if (l > r) {
            res.add(null);
            return res;
        }
        for (int i = l; i <= r; i++) {
            List<TreeNode> left = generateTrees(l, i - 1);
            List<TreeNode> right = generateTrees(i + 1, r);
            for (TreeNode ol : left) {
                for (TreeNode or : right) {
                    res.add(new TreeNode(i, ol, or));
                }
            }
        }
        return res;
    }
}

894. 所有可能的真二叉树 ​

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

结构类的枚举, 数量映射结构集

java
class Solution {
    private final Map<Integer, List<TreeNode>> cache = new HashMap<>();

    public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> res;
        if ((res = cache.get(n)) != null) return res;
        res = new ArrayList<>();
        if (n % 2 == 0) return res;
        TreeNode root = new TreeNode();
        if (n == 1) {
            res.add(root);
            cache.put(n, res);
            return res;
        }
        for (int i = 1; i <= n - 2; i += 2) {
            List<TreeNode> left = allPossibleFBT(i);
            List<TreeNode> right = allPossibleFBT(n - i - 1);
            for (var l : left) {
                for (var r : right) {
                    root = new TreeNode(0, l, r);
                    res.add(root);
                }
            }
        }
        cache.put(n, res);
        return res;
    }
}

路径搜索 ​

113. 路径总和 II mid ​

剑指 Offer 34. 二叉树中和为某一值的路径

给你二叉树的根节点 root 和一个整数目标和 target, 找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

回溯

从根节点到叶节点(严格)

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

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) return res;
        backtrace(root, target, new ArrayList<>());
        return res;
    }

    void backtrace(TreeNode node, int diff, List<Integer> list) {
        list.add(node.val);
        if (node.left == null && node.right == null) {
            if (diff == node.val) res.add(new ArrayList<>(list));
            list.remove(list.size() - 1);
            return;
        }
        if (node.left != null) backtrace(node.left, diff - node.val, list);
        if (node.right != null) backtrace(node.right, diff - node.val, list);
        list.remove(list.size() - 1);
    }
}

437. 路径总和 III mid ​

LCR 050. 路径总和 III

给定一个二叉树的根节点 root, 和一个整数(有负数) targetSum, 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始, 也不需要在叶子节点结束, 但是路径方向必须是向下的（只能从父节点到子节点）。

解法 dfs+树上前缀和

在线搜索, 在某个节点上, 计算以当前节点为右端点的区间和的数量, 只要知道根到此节点之前每个节点的前缀和所对应的数目, 就能求得路径和的数目.

java
class Solution {
    private final Map<Long, Integer> sumCnt = new HashMap<>();
    private int targetSum;

    public int pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        sumCnt.put(0L, 1);
        return dfs(root, 0);
    }

    // 返回 子树中满足的数量
    public int dfs(TreeNode root, long total) {
        if (root == null) return 0;
        total += root.val;
        // 计算以当前节点为右端点的区间和的数量
        int res = sumCnt.getOrDefault(total - targetSum, 0);
        sumCnt.merge(total, 1, Integer::sum);
        res += dfs(root.left, total);
        res += dfs(root.right, total);
        sumCnt.merge(total, -1, Integer::sum);
        return res;
    }
}

反转 ​

226. 翻转二叉树 easy ​

剑指 Offer 27. 二叉树的镜像

给你一棵二叉树的根节点 root, 翻转这棵二叉树, 并返回其根节点。

从根到叶和从叶子到根都行, 跟 反转二进制数字 类似呦

java
class Solution {
    public TreeNode invertTree(TreeNode root) {
        invert(root);
        return root;
    }

    private void invert(TreeNode node) {
        if (node == null) return;

        invert(node.left);
        invert(node.right);

        TreeNode temp;
        temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

BST ​

173. 二叉搜索树迭代器 mid ​

LCR 055. 二叉搜索树迭代器

实现一个二叉搜索树迭代器类 BSTIterator, 表示一个按中序遍历二叉搜索树（BST）的迭代器：

  • BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字, 且该数字小于 BST 中的任何元素。
  • boolean hasNext() 如果向指针右侧遍历存在数字, 则返回 true；否则返回 false。
  • int next() 将指针向右移动, 然后返回指针处的数字。

注意, 指针初始化为一个不存在于 BST 中的数字, 所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的, 也就是说, 当调用 next() 时, BST 的中序遍历中至少存在一个下一个数字。

解法 1 队列转数组 略

解法 2 栈

从随机某个节点开始继续处理的能力
栈式中序遍历

java
class BSTIterator {
    // 指向下次要处理的节点
    private TreeNode p;
    private final Deque<TreeNode> stack = new ArrayDeque<>();

    public BSTIterator(TreeNode root) {
        this.p = root;
    }

    public int next() {
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        TreeNode top = stack.pop();
        // 指向没处理的 right
        p = top.right;
        return top.val;
    }

    public boolean hasNext() {
        return p != null || !stack.isEmpty();
    }
}

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

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

解法 1: 迭代法

java
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (--k == 0) break;
            root = root.right;
        }
        return root.val;
    }
}

解法 2: 递归法

java
class Solution {
    int k;
    TreeNode res = null;

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        search(root);
        return res.val;
    }

    private void search(TreeNode root) {
        if (root == null) return;
        search(root.left);
        if (res != null) return;
        if (--k == 0) {
            res = root;
            return;
        }
        search(root.right);
    }
}

285. 二叉搜索树中的中序后继 mid ​

LCR 053. 二叉搜索树中的中序后继

给定一棵二叉搜索树和其中的一个节点 p，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

java
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode res = null;
        // 如果有右子树, 一定在右子树的最左边
        if (res.right != null) {
            res = res.right;
            while (res.left != null) {
                res = res.left;
            }
            return res;
        }
        // 二分
        while (root != null) {
            if (root.val > p.val) {
                res = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return res;
    }
}

501. 二叉搜索树中的众数 easy ​

给你一个含重复值的二叉搜索树（BST）的根节点 root, 找出并返回 BST 中的所有 众数（即, 出现频率最高的元素）。

如果树中有不止一个众数, 可以按 任意顺序 返回。

解法 中序遍历

中序遍历 BST 从小到大
维护 pre, pre 的重复次数, 最大重复次数, 结果集

java
public class Solution {
    List<Integer> list = new ArrayList<>();
    // 前值
    Integer pre;
    // 当前值的重复次数
    int cnt = 0;
    // 最大重复次数
    int max = 0;

    public int[] findMode(TreeNode root) {
        this.find(root);
        return list.stream().mapToInt(o -> o).toArray();
    }

    private void find(TreeNode root) {
        if (root == null) return;
        find(root.left);

        if (pre != null && pre == root.val) cnt++;
        else cnt = 1;
        pre = root.val;

        if (cnt == max) list.add(pre);
        else if (cnt > max) {
            max = cnt;
            list.clear();
            list.add(root.val);
        }
        find(root.right);
    }
}

530. 二叉搜索树的最小绝对差 easy ​

给你一个二叉搜索树的根节点 root，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

解法 中序遍历

java
public class Solution {
    int res = Integer.MAX_VALUE;
    Integer pre;

    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return res;
    }

    private void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.left);
        if (pre != null) res = Math.min(res, node.val - pre);
        pre = node.val;
        dfs(node.right);
    }
}

538. 把二叉搜索树转换为累加树 mid ​

1038
LCR 054. 把二叉搜索树转换为累加树

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

解法 倒序累加

大于的节点不一定只在右子树, 也可能在父节点

java
class Solution {

    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        sum(root);
        return root;
    }

    private void sum(TreeNode node) {
        if (node == null) return;
        sum(node.right);
        node.val = sum = node.val + sum;
        sum(node.left);
    }
}

653. 两数之和 IV easy ​

LCR 056. 两数之和 IV - 输入二叉搜索树

给定一个二叉搜索树 root 和一个目标结果 k, 如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true.

解法比较多, Set、转数组用双指针、栈加双指针
利用 BST 也需要额外的空间, 直接用 Set 简单方便

java
public class Solution {
    Set<Integer> set = new HashSet<>();

    public boolean findTarget(TreeNode root, int k) {
        if (root == null) return false;
        if (set.contains(k - root.val)) return true;
        set.add(root.val);
        return findTarget(root.left, k) || findTarget(root.right, k);
    }
}

669. 修剪二叉搜索树 mid ​

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

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

解法 递归

  1. 根节点在范围内
  2. 根节点不在范围内
java
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;
    }
}

700. 二叉搜索树中的搜索 easy ​

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

java
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        return search(root, val);
    }

    private TreeNode search(TreeNode node, int val) {
        if (node == null) return null;
        if (node.val == val)
            return node;
        if (node.val < val)
            return search(node.right, val);
        else
            return search(node.left, val);
    }
}

公共祖先 ​

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

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

满足左边的节点小于等于祖先, 右边的节点大于等于祖先

解法 1 迭代

java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode res = root;
        while (true) {
            if (p.val < res.val && q.val < res.val) {
                res = res.left;
            } else if (p.val > res.val && q.val > res.val) {
                res = res.right;
            } else {
                break;
            }
        }
        return res;
    }
}

解法 2 递归

java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
        if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

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

剑指 Offer 68 - II. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

解法 1 递归

左右两边找, 如果一左一右, 那就是根节点; 或者一个是另一个的子节点;

java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 一个也没找到 返null
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 左边没找到,右边是; 右边没找到, 左边是; 都找到了root是
        return left == null
                ? right : right == null
                ? left
                : root;
    }
}

解法 2 记录父节点

笨比解法

树相等 ​

572. 另一棵树的子树 easy ​

给你两棵二叉树 root 和 subRoot。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true；否则，返回 false。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

解法 判断 2 颗树是否相等

java
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return isEqual(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean isEqual(TreeNode root, TreeNode subRoot) {
        if (root == subRoot) return true;
        if (root == null || subRoot == null || root.val != subRoot.val) return false;
        return isEqual(root.left, subRoot.left) && isEqual(root.right, subRoot.right);
    }
}

还可以转成序列, 用 KMP