0100. Same Tree

题目信息

题号:
  1. 相同的树

难度:

Easy

主题:

二叉树、递归、广度优先搜索、深度优先搜索

原题:

LeetCode 0100

重点:

从带空标记的完整表示,推导到直接同步比较对应节点

题目重述

给定两棵二叉树 p 和 q,判断它们是否完全相同。

完全相同需要同时满足:

  • 两棵树在每个对应位置都同时为空或同时存在节点;

  • 每一对对应非空节点的值相等;

  • 左孩子只能与左孩子对应,右孩子只能与右孩子对应。

两棵树的节点数都在 0..100 范围内,节点值在 -10^4..10^4 范围内。

自建示例

输入:
p(层序)= [7,3,9,null,5]
q(层序)= [7,3,9,5]

输出:false

两棵树包含相同的节点值,但值 5 在 p 中是节点 3 的右孩子,在 q 中是左孩子, 对应位置的空节点不同。

输入:
p(层序)= [4,2,6]
q(层序)= [4,2,6]

输出:true

每个对应位置的结构和节点值都相同。

输入:p = [],q = []
输出:true

两个根节点都为空时,两棵空树完全相同。

C++ 实现

#include <queue>
#include <stack>
#include <string>
#include <utility>

class Solution {
private:
    void serialize(TreeNode* node, std::string& output) {
        if (!node) {
            output += "#,";
            return;
        }

        output += std::to_string(node->val) + ",";
        serialize(node->left, output);
        serialize(node->right, output);
    }

    bool serializedComparison(TreeNode* first, TreeNode* second) {
        std::string first_tree;
        std::string second_tree;
        serialize(first, first_tree);
        serialize(second, second_tree);
        return first_tree == second_tree;
    }

    bool recursivePair(TreeNode* first, TreeNode* second) {
        if (!first || !second) {
            return first == second;
        }
        if (first->val != second->val) {
            return false;
        }

        return recursivePair(first->left, second->left) &&
               recursivePair(first->right, second->right);
    }

    bool breadthFirstPairs(TreeNode* first, TreeNode* second) {
        std::queue<std::pair<TreeNode*, TreeNode*>> pending;
        pending.push({first, second});

        while (!pending.empty()) {
            auto [left_tree, right_tree] = pending.front();
            pending.pop();

            if (!left_tree || !right_tree) {
                if (left_tree != right_tree) {
                    return false;
                }
                continue;
            }
            if (left_tree->val != right_tree->val) {
                return false;
            }

            pending.push({left_tree->left, right_tree->left});
            pending.push({left_tree->right, right_tree->right});
        }
        return true;
    }

    bool depthFirstPairs(TreeNode* first, TreeNode* second) {
        std::stack<std::pair<TreeNode*, TreeNode*>> pending;
        pending.push({first, second});

        while (!pending.empty()) {
            auto [left_tree, right_tree] = pending.top();
            pending.pop();

            if (!left_tree || !right_tree) {
                if (left_tree != right_tree) {
                    return false;
                }
                continue;
            }
            if (left_tree->val != right_tree->val) {
                return false;
            }

            pending.push({left_tree->right, right_tree->right});
            pending.push({left_tree->left, right_tree->left});
        }
        return true;
    }

public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return recursivePair(p, q);
    }
};

题解

遍历值不足

只记录非空节点的遍历值会丢失结构。例如下面两棵树的前序值都为 1,2:

  1          1
 /            \
2              2

因此完整序列化必须同时写入空节点标记。前序序列化中的 #, 表示一个确定的空位置, 逗号则避免 1,23 与 12,3 一类拼接歧义。两份完整表示相同,树的值和结构才都相同。

成对状态

序列化分别构造两棵树的完整表示,但真正需要检查的是每一对对应位置。 定义 same(first, second) 为两棵对应子树是否完全相同,每次只有三种情况:

  1. 两者都为空,当前位置相同;

  2. 只有一者为空,结构已经不同;

  3. 两者都非空,先比较值,再比较左右同方向子树。

same(first, second) =
    first.value == second.value
    AND same(first.left,  second.left)
    AND same(first.right, second.right)

空节点配对

条件 if (!first || !second) return first == second 同时处理两个空节点分支:

  • 两者都是 nullptr,指针相等,返回 true;

  • 只有一个是 nullptr,指针不等,返回 false。

空节点不是可以忽略的数据缺失,而是树形的一部分。示例中左孩子与右孩子互换, 正是在某个对应位置形成 (nullptr, node),因此立即失败。

方向保持

本题比较的是相同树,不是镜像树。递归必须固定比较:

first.left  对 second.left
first.right 对 second.right

若交叉比较左右孩子,判断的将是镜像关系,无法保证对应位置一致。

递归完整性

根节点对检查完成后,问题被拆成左右两个互不重叠的子树对。每个节点只有唯一父节点, 所以每个对应位置最多访问一次。任意值差异会在非空节点比较时发现,任意结构差异会在 空节点配对时发现;全部递归分支都返回真时,两棵树的所有对应位置均相同。

显式容器

递归调用栈保存尚待比较的节点对。也可以把这些状态放入显式容器:

  • 队列按层比较,先发现靠近根部的差异;

  • 栈按深度比较,与递归控制流接近;

  • 两者弹出节点对后,都执行相同的空节点和值检查。

队列和栈只改变状态处理顺序,不改变判断规则。发现首个差异时都可以立即返回 false。

复杂度

设两棵树较小节点数为 n,完全相同时需要比较全部对应节点,时间为 O(n)。 递归和显式栈最多保存 O(h) 个沿深度方向的状态,h 为树高;队列最坏保存 O(n) 个同层节点对。序列化方法还需要 O(n) 中间字符串空间。