951. Flip Equivalent Binary Trees

我不是女神ヾ 2022-03-26 07:56 94阅读 0赞

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.

**Note:**

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

/**
     * 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==NULL && root2==NULL)
             return true;
          else if(root1==NULL || root2==NULL)
             return false;
          
          if(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)) ;
         
        } 
        
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，94人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode: Balanced Binary Tree

题目： Given a binary tree, determine if it is height-balanced. For this problem, a heig

傷城~/ 2022年08月07日 04:35/ 0 赞/ 198 阅读

相关 110. Balanced Binary Tree

题目描述： Given a binary tree, determine if it is height-balanced. For this problem, a hei

阳光穿透心脏的1/2处/ 2022年06月08日 14:59/ 0 赞/ 212 阅读

相关 654. Maximum Binary Tree

654. Maximum Binary Tree ![这里写图片描述][SouthEast] 这道题是中等难度的题目，一开始想到的解法是选择递归，因为这个问题本身就是递

深碍√TFBOYSˉ_/ 2022年06月04日 00:47/ 0 赞/ 205 阅读

相关 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

系统管理员/ 2022年03月26日 08:59/ 0 赞/ 218 阅读

相关 951. Flip Equivalent Binary Trees

For a binary tree T, we can define a flip operation as follows: choose any node, and swa

我不是女神ヾ/ 2022年03月26日 07:56/ 0 赞/ 95 阅读

相关 Invert Binary Tree

Invert a binary tree. 4 / \ 2 7 / \ / \ 1 3 6 9

太过爱你忘了你带给我的痛/ 2021年12月17日 10:41/ 0 赞/ 247 阅读

相关 Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...

刺骨的言语ヽ痛彻心扉/ 2021年12月17日 10:29/ 0 赞/ 247 阅读

相关 LeetCode 951. Flip Equivalent Binary Trees

原题链接在这里：[https://leetcode.com/problems/flip-equivalent-binary-trees/][https_leetcode.com

红太狼/ 2021年12月16日 23:41/ 0 赞/ 122 阅读

相关 [LintCode] Binary Tree Serialization

Design an algorithm and write code to serialize and deserialize a binary tree. Writing t

- 日理万妓/ 2021年12月03日 07:15/ 0 赞/ 242 阅读

相关 Binary Tree Tilt

Given a binary tree, return the tilt of the whole tree. The tilt of a tree node is defi

古城微笑少年丶/ 2021年10月01日 07:56/ 0 赞/ 261 阅读