Similar Trees with Leaf-Like Leaves#

Please consider all the leaves on a binary tree, and arrange the values of these leaves in the order from left to right to form a leaf value sequence.

Example#

For example, as shown in the figure above, given a tree with a leaf value sequence of (6, 7, 4, 9, 8). If the leaf value sequences of two binary trees are the same, then we consider them to be leaf-like. If the trees with the given root nodes root1 and root2 are leaf-like, return true; otherwise, return false.

Solution#

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function(root1, root2) {
    var dfs = function(root, target) {
        if(!root) return ;
        if(!root.left && !root.right) {
            target.push(root.val);
            return ;
        }
        if(root.left) dfs(root.left, target);
        if(root.right) dfs(root.right, target);
    }
    var target1 = [];
    var target2 = [];
    dfs(root1, target1);
    dfs(root2, target2);
    var n1 = target1.length;
    var n2 = target2.length;
    if(n1 !== n2) return false;
    for(let i=0;i<n1;++i){
        if(target1[i] !== target2[i]) return false;
    }
    return true;
};

Idea#

For two binary trees, first define a deep recursive traversal function to get all leaf nodes from left to right, and then compare whether all leaves are the same, so as to determine whether these two trees are leaf-like. First, define the deep recursive traversal function dfs. If the current node is null, it will no longer be recursively traversed downwards. If there is no leaf node in the left child, then the current node is considered as a leaf node, and then push it into the target target array, and then recursive traversal ends. If there is a left child, continue to recursively traverse to the left; if there is a right child, continue to recursively traverse to the right. Then push the leaf nodes of root1 and root2 into the target1 and target2 arrays respectively, then compare the array lengths. If they are different, return false directly. If they are the same, compare each value. If they are different, return false directly. If all are the same, return true in the end.

Daily Topic#

Reference#