tweaked identical binary tree

frontoldman 發布于2019-08-14 17:07 / 997人閱讀

摘要：原題檢查兩棵二叉樹是否在經過若干次扭轉后可以等價。扭轉的定義是，交換任意節點的左右子樹。等價的定義是，兩棵二叉樹必須為相同的結構，并且對應位置上的節點的值要相等。樣例是扭轉后可等價的二叉樹。

原題
檢查兩棵二叉樹是否在經過若干次扭轉后可以等價。扭轉的定義是，交換任意節點的左右子樹。等價的定義是，兩棵二叉樹必須為相同的結構，并且對應位置上的節點的值要相等。
注意：你可以假設二叉樹中不會有重復的節點值。
樣例

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;
    }

GPU云服務器云服務器 binary-tree binary-search-tree Identical Tweaks

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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