Tweaked Identical Binary Tree (Ladder)

Description

Check two given binary trees are identical or not. Assuming any number of tweaks are allowed. A tweak is defined as a swap of the children of one node in the tree.

Notice
There is no two nodes with the same value in the tree.

Example:

    1             1
   / \           / \
  2   3   and   3   2
 /                   \
4                     4

are identical.

    1             1
   / \           / \
  2   3   and   3   2
 /             /
4             4

are not identical.

Challenge:
O(n) time

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   /**
   * Definition of TreeNode:
   * class TreeNode {
   * public:
   *     int val;
   *     TreeNode *left, *right;
   *     TreeNode(int val) {
   *         this->val = val;
   *         this->left = this->right = NULL;
   *     }
   * }
   */
   class Solution {
   public:
    /**
     * @aaram a, b, the root of binary trees.
     * @return true if they are tweaked identical, or false.
     */
    bool isTweakedIdentical(TreeNode* a, TreeNode* b) {
        // Write your code here
        // a, b = nullptr
        if (!a && !b) {
            return true;
        }
        // !a b or a !b
        if (!a || !b) {
            return false;
        }
        // after here, must have a && b
        // same structure/diff value
        if (a->val != b->val) {
            return false;
        }
        // -----------------------------------------------
        // // Raw style
        // return isTweakedIdentical(a->left, b->left) 
        //     && isTweakedIdentical(a->right, b->right)
        //     || isTweakedIdentical(a->left, b->right)
        //     && isTweakedIdentical(a->right, b->left);
        // -----------------------------------------------
        // Better style 
        // same next level structure && same value
        if (isTweakedIdentical(a->left, b->left) 
            && isTweakedIdentical(a->right, b->right)
        ) {
            return true;
        }
        // tweaked next level structure && tweaked rest value
        if (isTweakedIdentical(a->left, b->right)
            && isTweakedIdentical(a->right, b->left)
        ) {
            return true;
        }
        // not even tweaked
        return false;
    }
   };
   

Similar problems

x

Tags

x