LeetCode.872-叶子值相等的树（Leaf-Similar Trees）

这是悦乐书的第334次更新，第358篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第204题（顺位题号是872）。考虑二叉树的所有叶子，从左到右的顺序，这些叶子的值形成叶子值序列。

例如，在上面给定的树中，叶子值序列是（6,7,4,9,8）。

如果两个二叉树的叶子值序列相同，则认为两个二叉树是叶子相似的。当且仅当具有头节点root1和root2的两个给定树是叶类似的时，才返回true。

注意：

两个给定的树将具有1到100个节点。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

题目的意思是给定两个二叉树，如果它们的叶子值都相等，就返回true。

也就是说，我们需要拿到二叉树的所有叶子节点的值，然后依次比较，如果相等就返回true。

从树的结构上来看，使用广度遍历的方式更好，整体思路就是使用广度优先算法，得到叶子节点值数组，再比较数组值判断是否相等。

此解法是借助栈，通过迭代的方式来实现广度优先算法。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {

        List<Integer> list = getLeafValue(root1);

        List<Integer> list2 = getLeafValue(root2);

        if (list.size() != list2.size()) {

            return false;

        }

        for (int i=0; i<list.size(); i++) {

            if (list.get(i) != list2.get(i)) {

                return false;

            }

        }

        return true;

    }

    public List getLeafValue(TreeNode root){

        List<Integer> list = new ArrayList<Integer>();

        Stack<TreeNode> stack = new Stack<TreeNode>();

        stack.push(root);

        while (!stack.isEmpty()) {

            int size = stack.size();

            for (int i=0; i<size; i++) {

                TreeNode node = stack.pop();

                if (node.left != null) {

                    stack.push(node.left);

                }

                if (node.right != null) {

                    stack.push(node.right);

                }

                if (node.left == null && node.right == null) {

                    list.add(node.val);

                }

            }

        }

        return list;

    }

}

03 第二种解法

针对广度优先算法，我们也可以使用递归的方式来实现。

递归方法中使用了两个参数，一是二叉树本身，二是存储叶子节点值的数组。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {

        List<Integer> list = new ArrayList<Integer>();

        List<Integer> list2 = new ArrayList<Integer>();

        getLeafValue(root1, list);

        getLeafValue(root2, list2);

        if (list.size() != list2.size()) {

            return false;

        }

        for (int i=0; i<list.size(); i++) {

            if (list.get(i) != list2.get(i)) {

                return false;

            }

        }

        return true;

    }

    public void getLeafValue(TreeNode root, List<Integer> list){

        if (root != null) {

            if (root.left == null && root.right == null) {

                list.add(root.val);

            }

            getLeafValue(root.left, list);

            getLeafValue(root.right, list);

        }

    }

}

04 第三种解法

在第二种解法的基础上，我们可以将数组换成字符串，思路和效果都是一样的。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {

        StringBuilder sb = new StringBuilder();

        StringBuilder sb2 = new StringBuilder();

        getLeafValue(root1, sb);

        getLeafValue(root2, sb2);

        return sb.toString().equals(sb2.toString());

    }

    public void getLeafValue(TreeNode root, StringBuilder sb){

        if (root != null) {

            if (root.left == null && root.right == null) {

                sb.append(root.val);

            }

            getLeafValue(root.left, sb);

            getLeafValue(root.right, sb);

        }

    }

}

05 小结

算法专题目前已连续日更超过六个月，算法题文章204+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！

巴特西