This is the first day of my participation in the August More Text challenge

preface

Algorithm and data structure have always been the shortcomings of my programming ability. In order to improve my ability in this aspect, I also started to systematically brush questions, and also sorted out some experience of brush questions into notes, coincides with this More article activity in August, let’s share it with you!

Topic:

Today is the first day of August. I’d like to share my topic with you: Trees with similar leaves. The topic is as follows:

Consider all the leaves on a binary tree whose values are arranged from left to right to form a sequence of leaf values.

For example, given a tree with a sequence of (6, 7, 4, 9, 8) leaf values, as shown in the figure above.

If two binary trees have the same sequence of leaf values, they are considered leaf similar.

Return true if two trees with roots root1 and root2 are leaf alike; Otherwise return false.

Example:

Input: root1 = [1], root2 = [1] Output: true Input: root1 = [1], root2 = [2] Output: false Input: root1 = [2], root2 = [2,2] Output: trueCopy the code

Answer:

First, we need to know what a leaf node is. In a binary tree, when both the left and right subtrees of a node are empty, we call the node a leaf node.

So to get the leaves of a tree, we can walk through the tree; Tree traversal is divided into depth-first traversal and breadth-first traversal. Students unfamiliar with these two traversal methods can first understand its meaning. Here, we use depth-first traversal to get the leaf value node of a tree, and then save its value into an array.

After obtaining the sequence of leaf values of the two trees, we can compare whether they are equal or not.

code

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        // Create two lists to store root1 and root2 leaves
        List<Integer> list1 = new ArrayList();
        List<Integer> list2 = new ArrayList();
        // Get the sequence of leaf nodes
        DFS(root1, list1);
        DFS(root2, list2);
        // Compare two sequences
        // If the length is different, it must not be similar
        if (list1.size() == list2.size()) {
            for (int i = 0; i < list1.size(); i++) {
                // Return false if one digit is not equal
                if(list1.get(i) ! = list2.get(i))return false; }}else {
            return false;
        }

        return true;
    }

    // depth-first search and add leaf nodes to the set
    public void DFS(TreeNode root, List<Integer> list){
        if (root == null) return;
        if (root.left == null && root.right == null) { list.add(root.val); } DFS(root.left, list); DFS(root.right, list); }}Copy the code

The last

The complexity analysis is as follows:

Time complexity: O(n1 + n2), where N1 and n2 are the number of nodes in two trees respectively.

Space complexity: O(N1 + n2), where the space complexity mainly depends on the space to store the sequence of leaf values and the stack space needed in the depth-first search process.