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

这是悦乐书的第334次升级，第358篇原创

01 看题和准备

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

image

例如，在上面给定的树中，叶子值序列是（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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

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