LC 872. 叶子相似的树

题目描述

这是 LeetCode 上的 872. 叶子相似的树 ，难度为简单。

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个叶值序列。

举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是叶相似的。

如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false。

示例 1：

输入：
root1 = [3,5,1,6,2,9,8,null,null,7,4], 
root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]

输出：true

示例 2：

1
2
3

输入：root1 = [1], root2 = [1]

输出：true

示例 3：

1
2
3

输入：root1 = [1], root2 = [2]

输出：false

示例 4：

1
2
3

输入：root1 = [1,2], root2 = [2,2]

输出：true

示例 5：

1
2
3

输入：root1 = [1,2,3], root2 = [1,3,2]

输出：false

提示：

给定的两棵树可能会有 1 到 200 个结点。
给定的两棵树上的值介于 0 到 200 之间。

递归

递归写法十分简单，属于树的遍历中最简单的实现方式。

Java 代码：

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
        dfs(root1, l1);
        dfs(root2, l2);
        if (l1.size() == l2.size()) {
            for (int i = 0; i < l1.size(); i++) {
                if (!l1.get(i).equals(l2.get(i))) return false;
            }
            return true;
        }
        return false;
    }
    void dfs(TreeNode root, List<Integer> list) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            list.add(root.val);
            return;
        }
        dfs(root.left, list);
        dfs(root.right, list);
    }
}

C++ 代码：

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> l1, l2;
        dfs(root1, l1);
        dfs(root2, l2);
        if (l1.size() == l2.size()) {
            return equal(l1.begin(), l1.end(), l2.begin());
        }
        return false;
    }
    void dfs(TreeNode* root, vector<int>& list) {
        if (!root) return;
        if (!root->left && !root->right) {
            list.push_back(root->val);
            return;
        }
        dfs(root->left, list);
        dfs(root->right, list);
    }
};

Python 代码：

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        l1, l2 = [], []
        self.dfs(root1, l1)
        self.dfs(root2, l2)
        if len(l1) == len(l2):
            return l1 == l2
        return False
    
    def dfs(self, root, list):
        if not root:
            return
        if not root.left and not root.right:
            list.append(root.val)
            return
        self.dfs(root.left, list)
        self.dfs(root.right, list)

TypeScript 代码：

function dfs(root: TreeNode | null, list: number[]): void {
    if (root === null) return;
    if (root.left === null && root.right === null) {
        list.push(root.val);
        return;
    }
    dfs(root.left, list);
    dfs(root.right, list);
}
function leafSimilar(root1: TreeNode | null, root2: TreeNode | null): boolean {
    const l1: number[] = [], l2: number[] = [];
    dfs(root1, l1);
    dfs(root2, l2);
    if (l1.length === l2.length) {
        return l1.every((val, index) => val === l2[index]);
    }
    return false;  
};

时间复杂度：n 和 m 分别代表两棵树的节点数量。复杂度为 $O(n + m)$
空间复杂度：n 和 m 分别代表两棵树的节点数量，当两棵树都只有一层的情况，所有的节点值都会被存储在 list 中。复杂度为 $O(n + m)$

迭代

迭代其实就是使用「栈」来模拟递归过程，也属于树的遍历中的常见实现形式。

一般简单的面试中如果问到树的遍历，面试官都不会对「递归」解法感到满意，因此掌握「迭代/非递归」写法同样重要。

Java 代码：

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
        process(root1, l1);
        process(root2, l2);
        if (l1.size() == l2.size()) {
            for (int i = 0; i < l1.size(); i++) {
                if (!l1.get(i).equals(l2.get(i))) return false;
            }
            return true;
        }
        return false;
    }
    void process(TreeNode root, List<Integer> list) {
        Deque<TreeNode> d = new ArrayDeque<>();
        while (root != null || !d.isEmpty()) {
            while (root != null) {
                d.addLast(root);
                root = root.left;
            }
            root = d.pollLast();
            if (root.left == null && root.right == null) list.add(root.val);
            root = root.right;
        }
    }
}

C++ 代码：

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> l1, l2;
        process(root1, l1);
        process(root2, l2);
        if (l1.size() == l2.size()) {
            for (int i = 0; i < l1.size(); i++) {
                if (l1[i] != l2[i]) return false;
            }
            return true;
        }
        return false;
    }
    void process(TreeNode* root, vector<int>& list) {
        deque<TreeNode*> d;
        while (root != nullptr || !d.empty()) {
            while (root != nullptr) {
                d.push_back(root);
                root = root->left;
            }
            root = d.back();
            d.pop_back();
            if (root->left == nullptr && root->right == nullptr) list.push_back(root->val);
            root = root->right;
        }
    }
};

Python 代码：

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        l1, l2 = [], []
        self.process(root1, l1)
        self.process(root2, l2)
        if len(l1) == len(l2):
            for i in range(len(l1)):
                if l1[i] != l2[i]:
                    return False
            return True
        return False
    
    def process(self, root, l):
        d = []
        while root or d:
            while root:
                d.append(root)
                root = root.left
            root = d.pop()
            if not root.left and not root.right:
                l.append(root.val)
            root = root.right

TypeScript 代码：

function process(root: TreeNode | null, list: number[]): void {
    const d: TreeNode[] = [];
    while (root != null || d.length != 0) {
        while (root != null) {
            d.push(root);
            root = root.left;
        }
        root = d.pop();
        if (root.left == null && root.right == null) list.push(root.val);
        root = root.right;
    }
}
function leafSimilar(root1: TreeNode | null, root2: TreeNode | null): boolean {
    const l1: number[] = [], l2: number[] = [];
    process(root1, l1);
    process(root2, l2);
    if (l1.length == l2.length) {
        for (let i = 0; i < l1.length; i++) {
            if (l1[i] != l2[i]) return false;
        }
        return true;
    }
    return false;
};

时间复杂度：n 和 m 分别代表两棵树的节点数量。复杂度为 $O(n + m)$
空间复杂度：n 和 m 分别代表两棵树的节点数量，当两棵树都只有一层的情况，所有的节点值都会被存储在 list 中。复杂度为 $O(n + m)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.872 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

DFS 树的搜索递归非递归

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 1734. 解码异或后的排列上一篇

LC 1482. 制作 m 束花所需的最少天数下一篇