tweaked identical binary tree

frontoldman 发布于2019-08-14 17:07 / 830人阅读

摘要：原题检查两棵二叉树是否在经过若干次扭转后可以等价。扭转的定义是，交换任意节点的左右子树。等价的定义是，两棵二叉树必须为相同的结构，并且对应位置上的节点的值要相等。样例是扭转后可等价的二叉树。

原题
检查两棵二叉树是否在经过若干次扭转后可以等价。扭转的定义是，交换任意节点的左右子树。等价的定义是，两棵二叉树必须为相同的结构，并且对应位置上的节点的值要相等。
注意：你可以假设二叉树中不会有重复的节点值。
样例

1             1

/ /
2 3 and 3 2
/
4 4
是扭转后可等价的二叉树。

1             1

/ /
2 3 and 3 2
/ /
4 4
就不是扭转后可以等价的二叉树。

解题思路
Recursion - 递归求解，分治的思路。
注意，题目中说的是经过若干次扭转后可以等价，所以不要忘记考虑完全identical的情况，某一个节点的左右子树翻转一次对称，反转两次还原。

文／Jason_Yuan（简书作者）
原文链接：http://www.jianshu.com/p/0623...

public boolean isTweakedIdentical(TreeNode a, TreeNode b) {
        if (a == null && b == null) {
            return true;
        }
        if (a == null || b == null) {
            return false;
        }
        if (a.val != b.val){
            return false;
        }
        //divide
        // boolean left = isTweakedIdentical(a.left, b.right);
        // boolean right = isTweakedIdentical(a.right, b.left);
        //注意，题目中说的是经过若干次扭转后可以等价，所以不要忘记考虑完全identical的情况，某一个节点的左右子树翻转一次对称，反转两次还原。
        boolean left = isTweakedIdentical(a.left, b.left) || isTweakedIdentical(a.left, b.right);
        boolean  right = isTweakedIdentical(a.right, b.right) || isTweakedIdentical(a.right, b.left);
        
        //conquer
        // if (left != true || right != true){
        //     return false;
        // }
        // else{
        //     return true;
        // }
        
        return left && right;
    }

专线服务私有云 binary-tree binary-search-tree Identical Tweaks

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66439.html

[LintCode] Identical Binary Tree

problem Check if two binary trees are identical. Identical means the two binary trees have the same structure and every identical position has the same value. Example 1 1 / ...

zoomdong 2019-08-14 15:11 评论0 收藏0
[Leetcode] Same Tree Symmetric Tree 相同树对称树

摘要：递归法复杂度时间空间递归栈空间思路如果两个根节点一个为空，一个不为空，或者两个根节点值不同，说明出现了不一样的地方，返回假。代码递归法复杂度时间空间递归栈空间思路其实和写法是一样的，是比较两个节点的两个左边，然后再比较两个节点的两个右边。 Same Tree Given two binary trees, write a function to check if they are eq...

TZLLOG 2019-08-14 12:32 评论0 收藏0
leetcode100 Same Tree 引发的对遍历?算法的思考

摘要：判断两棵树是否是相同题目要求传入两棵树的根节点，判断这两棵树是否相同此题的核心就在于如何遍历树。定义树的一种自然方式是递归的方式。一棵树是一些节点的集合，这个集合可以是空集。这个遍历算法可以用于场景如，计算一个节点的高度。判断两棵树是否是相同题目要求：传入两棵树的根节点，判断这两棵树是否相同此题的核心就在于如何遍历树。一旦我们解决了这个问题，题目也就迎刃而解了。下面就来介绍一下关...

cyrils 2019-08-14 17:52 评论0 收藏0
多标签(组)运算

摘要：代码实现测试代码输出解析标签表达式基础的表达式解析实现了，针对我们的标签表达式多个字符组成一个标签，以及去掉，加上的逻辑，稍作修改测试代码输出后缀表达式转二叉树分析根据后缀表达式的含义，符合表示前面两个元素的运算。用户标签是个数组。一、概述标签是精细化运营必不可少的工具，常见的使用场景有标签推送，千人千面的广告展示等。在实际的业务中，标签往往是通过交并差非运算组合在一起使用，比如：...

Developer 2019-07-01 11:08 评论0 收藏0