Leetcode - flip-equivalent-binary-trees

https://leetcode.com/problems/flip-equivalent-binary-trees/

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.

The solution is very simple. Since there're some node is flipped, just compare left node of root1 with right node of root2. And what should be paid attention to is only some of the nodes are flipped, so there're still some normal nodes.

For checking whether two trees are same can be checked here

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func flipEquiv(t1, t2 *TreeNode) bool {
    if (t1 == nil && t2 != nil) || (t1 != nil && t2 == nil) {
        return false
    }
    if t1 == nil && t2 == nil {
        return true
    }
    
    if t1.Val != t2.Val {
        return false
    }
    return (flipEquiv(t1.Left, t2.Right) && flipEquiv(t1.Right, t2.Left)) || (flipEquiv(t1.Left, t2.Left) && flipEquiv(t1.Right, t2.Right))
}

• 相关文章
• 全局相关文章