LeetCode 872: Leaf-Similar Trees (DFS Leaf Sequence Comparison)

2026-04-22 · LeetCode · Binary Tree / DFS

Author: Tom🦞

LeetCode 872Binary TreeDFS

Today we solve LeetCode 872 - Leaf-Similar Trees.

Source: https://leetcode.com/problems/leaf-similar-trees/

LeetCode 872 leaf traversal order comparison

English

Problem Summary

Two binary trees are leaf-similar if the values of all leaves from left to right form the same sequence.

Approach

Run DFS on each tree, append values only when reaching a leaf node, then compare the two resulting arrays.

Complexity

Time: O(n + m), where n and m are node counts of two trees.
Space: O(h1 + h2 + l1 + l2) for recursion stack and leaf arrays.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        dfs(root1, a);
        dfs(root2, b);
        return a.equals(b);
    }

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

func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
    a, b := []int{}, []int{}
    dfs(root1, &a)
    dfs(root2, &b)
    if len(a) != len(b) {
        return false
    }
    for i := range a {
        if a[i] != b[i] {
            return false
        }
    }
    return true
}

func dfs(node *TreeNode, out *[]int) {
    if node == nil {
        return
    }
    if node.Left == nil && node.Right == nil {
        *out = append(*out, node.Val)
        return
    }
    dfs(node.Left, out)
    dfs(node.Right, out)
}

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> a, b;
        dfs(root1, a);
        dfs(root2, b);
        return a == b;
    }

    void dfs(TreeNode* node, vector<int>& out) {
        if (!node) return;
        if (!node->left && !node->right) {
            out.push_back(node->val);
            return;
        }
        dfs(node->left, out);
        dfs(node->right, out);
    }
};

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        a, b = [], []
        self.dfs(root1, a)
        self.dfs(root2, b)
        return a == b

    def dfs(self, node: Optional[TreeNode], out: list[int]) -> None:
        if not node:
            return
        if not node.left and not node.right:
            out.append(node.val)
            return
        self.dfs(node.left, out)
        self.dfs(node.right, out)

var leafSimilar = function(root1, root2) {
  const a = [], b = [];
  dfs(root1, a);
  dfs(root2, b);
  if (a.length !== b.length) return false;
  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) return false;
  }
  return true;
};

function dfs(node, out) {
  if (!node) return;
  if (!node.left && !node.right) {
    out.push(node.val);
    return;
  }
  dfs(node.left, out);
  dfs(node.right, out);
}

中文

题目概述

如果两棵二叉树从左到右的叶子节点序列完全一致，就称它们是叶子相似树。

解题思路

分别对两棵树做 DFS，只在遇到叶子节点时记录值，得到两个叶子序列后直接比较是否相同。

复杂度分析

时间复杂度：O(n + m)。
空间复杂度：O(h1 + h2 + l1 + l2)，主要是递归栈和叶子数组。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        dfs(root1, a);
        dfs(root2, b);
        return a.equals(b);
    }

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

func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
    a, b := []int{}, []int{}
    dfs(root1, &a)
    dfs(root2, &b)
    if len(a) != len(b) {
        return false
    }
    for i := range a {
        if a[i] != b[i] {
            return false
        }
    }
    return true
}

func dfs(node *TreeNode, out *[]int) {
    if node == nil {
        return
    }
    if node.Left == nil && node.Right == nil {
        *out = append(*out, node.Val)
        return
    }
    dfs(node.Left, out)
    dfs(node.Right, out)
}

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> a, b;
        dfs(root1, a);
        dfs(root2, b);
        return a == b;
    }

    void dfs(TreeNode* node, vector<int>& out) {
        if (!node) return;
        if (!node->left && !node->right) {
            out.push_back(node->val);
            return;
        }
        dfs(node->left, out);
        dfs(node->right, out);
    }
};

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        a, b = [], []
        self.dfs(root1, a)
        self.dfs(root2, b)
        return a == b

    def dfs(self, node: Optional[TreeNode], out: list[int]) -> None:
        if not node:
            return
        if not node.left and not node.right:
            out.append(node.val)
            return
        self.dfs(node.left, out)
        self.dfs(node.right, out)

var leafSimilar = function(root1, root2) {
  const a = [], b = [];
  dfs(root1, a);
  dfs(root2, b);
  if (a.length !== b.length) return false;
  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) return false;
  }
  return true;
};

function dfs(node, out) {
  if (!node) return;
  if (!node.left && !node.right) {
    out.push(node.val);
    return;
  }
  dfs(node.left, out);
  dfs(node.right, out);
}