872.Leaf-Similar Trees

tags: Easy,Tree,Binary Tree,DFS

872. Leaf-Similar Trees

題目描述

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

範例

Example 1:

Input: 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]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

• The number of nodes in each tree will be in the range [1, 200].
• Both of the given trees will have values in the range [0, 200].

解答

C#

public class Solution {
    public bool LeafSimilar(TreeNode root1, TreeNode root2) {
        var list1 = PreorderLeaves(root1).GetEnumerator();
        var list2 = PreorderLeaves(root2).GetEnumerator();
        
        while (list1.MoveNext()) {
            if (!list2.MoveNext() || 
                list1.Current != list2.Current) {
                return false;
            }
        }
        if (list2.MoveNext()) return false;
        return true;
    }

    private IEnumerable<int> PreorderLeaves(TreeNode root) {
        var stack = new Stack<TreeNode>();
        stack.Push(root);

        while (stack.Count > 0) {
            var node = stack.Pop();
            if (node.left == null && node.right == null) {
                yield return node.val;
            }
            if (node.right != null) {
                stack.Push(node.right);
            }
            if (node.left != null) {
                stack.Push(node.left);
            }
        }
    }

遞迴版本

public class Solution {
    public bool LeafSimilar(TreeNode root1, TreeNode root2) {
        return Dfs(root1).SequenceEqual(Dfs(root2));
    }

    private IEnumerable<int> Dfs(TreeNode node) {
        if (node.left == null && node.right == null) {
            yield return node.val;
        }
        if (node.left != null) {
            foreach (int val in Dfs(node.left)) {
                yield return val;
            }
        }
        if (node.right != null) {
            foreach (int val in Dfs(node.right)) {
                yield return val;
            }
        }
    }
}

Jim Dec 8, 2022

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def findLeaf(root):
            res, l_res, r_res = [], [], []
            
            if not root.left and not root.right:
                res.append(root.val)

            if root.left:
                l_res = findLeaf(root.left)
            if root.right:
                r_res = findLeaf(root.right)

            return res + l_res + r_res

        return findLeaf(root1) == findLeaf(root2)

Kobe Dec 8, 2022

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def dfs(root):
            if root:
                if not root.left and not root.right:
                    yield root.val
                for v in dfs(root.left):
                    yield v
                for v in dfs(root.right):
                    yield v
        return list(dfs(root1)) == list(dfs(root2))

Yen-Chi ChenThu, Dec 8, 2022

C++

class Solution {
public:
    void dfs(TreeNode* root, vector<int>& leaves) {
        if (!root) return;
        if (!root->left && !root->right) leaves.push_back(root->val);
        dfs(root->left, leaves);
        dfs(root->right, leaves);
    }
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> leaves1, leaves2;
        dfs(root1, leaves1);
        dfs(root2, leaves2);
        return leaves1 == leaves2;
    }
};

Yen-Chi ChenThu, Dec 8, 2022

Javascript

function leafSimilar(root1, root2) {
  return findLeaf(root1).toString() === findLeaf(root2).toString();
}

function findLeaf(root) {
  const leaf = [];
  if (root === null) return leaf;

  if (root.left === null && root.right === null) {
    leaf.push(root.val);
  }

  leaf.push(...findLeaf(root.left));
  leaf.push(...findLeaf(root.right));

  return leaf;
}

Marsgoat Dec 8, 2022

Reference

回到題目列表