Binary Tree (3)

2021-08-19

0. 前言

东哥手把手带你刷二叉树|第三期 (qq.com)

本文着重讲讲如何判断在二叉树的题目中到底应该用前序、中序、还是后序遍历的框架。

关键在于了解题意，思考一个二叉树节点到底需要做什么。

1. 654 - 寻找重复的子树

分析

函数签名：List<TreeNode> findDuplicateSubtrees(TreeNode root);

输入：二叉树 root node

输出：所有重复的子树的 root node list

重复的定义：结构相同、结点值相同

思路：

思考每个节点要做的事情，它需要判断自己是不是一个重复子树的 root node，假如是就要加入 result list；
如何判断？知道我的子树的结构以及以其他节点为根的子树的结构。

难点 1：如何知道自己的子树的结构？

既然想知道左右子树的情况，那么我们很显然应该用后序遍历。

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
    /* 解法代码的位置 */
}

比如我们想知道整个二叉树的节点数量，也是用类似的后序遍历框架：

int count(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 先算出左右子树有多少节点
    int left = count(root.left);
    int right = count(root.right);
    /* 后序遍历代码位置 */
    // 加上自己，就是整棵二叉树的节点数
    int res = left + right + 1;
    return res;
}

那么如何去描述二叉树的结构呢？我们可以把所有的 node value 合并成一个 string，通过对比 string 来判断自己和别人是否长得一样。

我们用 # 来表示 null，用 , 来分割每个节点的值；
按照左子树、右子树、根节点的顺序来拼接 -> 后序遍历顺序（PS：这里是为了对应解题思路，我们也可以用其他两种遍历框架来做拼接）；

相关阅读：二叉树的序列化和反序列化

String traverse(TreeNode root) {
    // 对于空节点，可以用一个特殊字符表示
    if (root == null) {
        return "#";
    }
    // 将左右子树序列化成字符串
    String left = traverse(root.left);
    String right = traverse(root.right);
    /* 后序遍历代码位置 */
    // 左右子树加上自己，就是以自己为根的二叉树序列化结果
    String subTree = left + "," + right + "," + root.val;
    return subTree;
}

难点 2：如何与别的二叉树的结构进行对比？

我们需要把每个二叉树的序列化结果存在一个数据结构里面，然后每当有一个新的序列化结果，就跟这个数据结构里面已有的 string 进行对比。

因为题目要求只返回重复的二叉树的 root node，所以我们用 HashMap 而不是 HashSet，因为 HashMap 可以记录每个子树的出现次数。

// 记录所有子树以及出现的次数
HashMap<String, Integer> memo = new HashMap<>();
// 记录重复的子树根节点
LinkedList<TreeNode> res = new LinkedList<>();

/* 主函数 */
List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    traverse(root);
    return res;
}

/* 辅助函数 */
String traverse(TreeNode root) {
    if (root == null) {
        return "#";
    }

    String left = traverse(root.left);
    String right = traverse(root.right);

    String subTree = left + "," + right+ "," + root.val;

    int freq = memo.getOrDefault(subTree, 0);
    // 多次重复也只会被加入结果集一次
    if (freq == 1) {
        res.add(root);
    }
    // 给子树对应的出现次数加一
    memo.put(subTree, freq + 1);
    return subTree;
}

用 HashSet 可以得到所有子树的非重复序列化结果，在这个题目里面不适用。

// 记录所有子树
HashSet<String> memo = new HashSet<>();
// 记录重复的子树根节点
LinkedList<TreeNode> res = new LinkedList<>();

String traverse(TreeNode root) {
    if (root == null) {
        return "#";
    }

    String left = traverse(root.left);
    String right = traverse(root.right);

    String subTree = left + "," + right+ "," + root.val;

    if (memo.contains(subTree)) {
        // 有人和我重复，把自己加入结果列表
        res.add(root);
    } else {
        // 暂时没人跟我重复，把自己加入集合
        memo.add(subTree);
    }
    return subTree;
}

完整代码

注意点：

判断是否加入 result list 要用 count == 1，因为多次重复只加一次；
counter increment 要用 ++count，而不能用 count++，因为我们要先计算新的值，再assign给dict；
- i++（后++）是先用后算，先把 i 的值用来做比较，再把 i 的值 + 1；
- ++i（前++）是先算后用，先把 i 的值 + 1，再使用这个新的值作比较；

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    HashMap<String, Integer> dict = new HashMap<>();
    LinkedList<TreeNode> duplicateRoots = new LinkedList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return duplicateRoots;
    }

    String traverse(TreeNode root){
        if (root == null){
            return "#";
        }

        String left = traverse(root.left);
        String right = traverse(root.right);

        String serialized = left + "," + right + "," + root.val;
        
        // if result is not in the dict, return 0 as count
        int count = dict.getOrDefault(serialized, 0);
				
        // only add once to the duplicateRoots, we cannot use count >= 1 here
        if (count == 1){
            duplicateRoots.add(root);
        }

        dict.put(serialized, count + 1); // dict.put(serialized, ++count);
        return serialized;
    }
}

Luna Tech