872. 叶子相似的树（二叉树使用了Morris算法）

本文主要是介绍872. 叶子相似的树（二叉树使用了Morris算法），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目来源：872. 叶子相似的树 // 请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。 // 举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。 // 如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。 // 如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。 解析： 　　这题难度为简单，如果熟悉二叉树的遍历确实不难，使用dfs，深度递归遍历获取叶子结点数组，然后比较。 　　最近刚刚学习了二叉树遍历节省空间的一种算法，Morris算法 　　但是在解此题的时候遇到了点小困难，Morris算法是利用叶子结点右子树为空的特性，将它指向中序遍历后继结点。这样就不能用是否左右子树为空来判断叶子结点了。 　　再次查看Morris算法的原理，叶子结点右子树为空时指向其中序遍历后继结点，遍历时再次还原为空，那么可以利用这一点。 　　1. 右子树在还原时判断如果左子树也为空则证明其为叶子结点 　　2. 查看是否还有遗漏的叶子结点，如果叶子结点为中序遍历最后一个结点，那么它是没有中序遍历后继结点的。此时左右子树均为空。 　　

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function(root1, root2) {
    let r1 = morris(root1);
    let r2 = morris(root2);
    return r1.join(',') === r2.join(',')
};
const morris=(root)=>{
    let cur = root;
    let res = [];
    while(cur){
        if(cur.left === null){
            if(cur.right === null){
                res.push(cur.val);
            }
            cur = cur.right;
        }else{
            let node = cur.left;
            while(node && node.right !== null && node.right !== cur){
                node = node.right;
            }
            if(node.right === null){
                node.right = cur;
                cur = cur.left;
            }else{
                if(node.left === null)res.push(node.val);
                node.right = null;
                cur = cur.right;
            }
        }
    }
    return res;
}

 

这篇关于872. 叶子相似的树（二叉树使用了Morris算法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！