How to Flip Equivalent Binary Trees?

  • 时间:2020-09-28 16:28:51
  • 分类:网络文摘
  • 阅读:81 次

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees. A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations. Write a function that determines whether two binary trees are flip equivalent. The trees are given by root nodes root1 and root2.

Example 1:
Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.

binary-flip-tree How to Flip Equivalent Binary Trees? algorithms c / c++

binary-flip-tree

Note:
Each tree will have at most 100 nodes.
Each value in each tree will be a unique integer in the range [0, 99].

Flip Binary Trees Algorithm using Depth First Search (Recursion)

The following C++ implementation of DFS runs at O(Min(N1, N2)) time complexity and O(Min(H1, H2)) space complexity where N1, N2 are the number of nodes and H1, H2 are the heights/depths of the binary trees.

The recursion defines the basic terminate conditions. If two nodes are both NULL (or they are equal), they are flip-equivalent binary trees. If only one node is NULL (another is not), or the values are not equal, then it is NOT a flip-equivalent binary tree. Otherwise, we recursively check two cases. Either both left sub-trees and both right sub-trees are flip equivalent binary trees, or the left sub tree (of tree 1) is flip equivalent to the right sub tree (of tree 2), and right sub tree (of tree 1) is flip equivalent to the left sub tree (of tree 2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if (root1 == root2) return true; // root1 == NULL && root2 == NULL
        if (root1 == NULL || root2 == NULL || root1->val != root2->val) return false;
        return (flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right)) ||
            (flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left));
    }    
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if (root1 == root2) return true; // root1 == NULL && root2 == NULL
        if (root1 == NULL || root2 == NULL || root1->val != root2->val) return false;
        return (flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right)) ||
            (flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left));
    }    
};

Canonical Traversal using Depth First Search (Recursion)

Another C++ solution (also based on DFS that is implemented in Recursion) is as follows where both trees are walked through using Canonical Traversal order (where the smaller node is visited first). Then we just have to compare the output sequences of both trees.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        vector<int> r1, r2;
        dfs(root1, r1);
        dfs(root2, r2);
        return same(r1, r2); // check if the order is the same
    }    
    
    void dfs(TreeNode* root, vector<int> &r) {
        if (root != NULL) {
            r.push_back(root->val);
            if (root->left == NULL) {
                dfs(root->right, r);
            } else 
            if (root->right == NULL) {
                dfs(root->left, r);
            } else
            if (root->left->val < root->right->val) {
                dfs(root->left, r);
                dfs(root->right, r);
            } else {
                dfs(root->right, r);
                dfs(root->left, r);                    
            }
            r.push_back(-1); // marks end
        }
    }
    
    bool same(const vector<int> &r1, const vector<int> &r2) {
        if (r1.size() != r2.size()) return false;
        for (int i = 0; i < r1.size(); ++ i) {
            if (r1[i] != r2[i]) return false;
        }
        return true;
    }
};
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        vector<int> r1, r2;
        dfs(root1, r1);
        dfs(root2, r2);
        return same(r1, r2); // check if the order is the same
    }    
    
    void dfs(TreeNode* root, vector<int> &r) {
        if (root != NULL) {
            r.push_back(root->val);
            if (root->left == NULL) {
                dfs(root->right, r);
            } else 
            if (root->right == NULL) {
                dfs(root->left, r);
            } else
            if (root->left->val < root->right->val) {
                dfs(root->left, r);
                dfs(root->right, r);
            } else {
                dfs(root->right, r);
                dfs(root->left, r);                    
            }
            r.push_back(-1); // marks end
        }
    }
    
    bool same(const vector<int> &r1, const vector<int> &r2) {
        if (r1.size() != r2.size()) return false;
        for (int i = 0; i < r1.size(); ++ i) {
            if (r1[i] != r2[i]) return false;
        }
        return true;
    }
};

The time complexity is O(N1 + N2 + Min(N1, N2) which is O(N1 + N2) because both trees have to be visited entirely. And the space complexity is O(N1 + N2) as additional space has to be allocated to store the Canonical Traversal sequences for both trees.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
熊掌号:博客优化的SEO技巧有哪些?  超级排名系统介绍 快速提升百度搜狗360神马手机网站排名  超级排名系统:常见的搜索引擎指令有哪些?  网站是靠什么途径赚钱的?怎么让你的网站赚钱?  个人站长如何赚钱?淘宝客还是卖广告位  一道往返问题  速算小诀窍  佛珠的数量  棋盘上的麦粒问题  喀氏数 
评论列表
添加评论