【leetcode】951. 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.

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.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    res = True
    def verify(self,node1,node2):
        leftV1 = None if node1.left == None else node1.left.val
        leftV2 = None if node2.left == None else node2.left.val
        rightV1 = None if node1.right == None else node1.right.val
        rightV2 = None if node2.right == None else node2.right.val
        if leftV1 == leftV2 and rightV1 == rightV2:
            return 0
        elif leftV1 == rightV2 and rightV1 == leftV2:
            return 1
        else:
            return -1
    def traverse(self,node1,node2):
        if node1 == None or node2 == None:
            return
        ret = self.verify(node1,node2)
        if ret == 0:
            self.traverse(node1.left,node2.left)
            self.traverse(node1.right, node2.right)
        elif ret == 1:
            node2.left,node2.right = node2.right,node2.left
            self.traverse(node1.left, node2.left)
            self.traverse(node1.right, node2.right)
        else:
            self.res = False

    def flipEquiv(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: bool
        """
        if (root1 == None) ^ (root2 == None):
            return False
        self.res = True
        self.traverse(root1,root2)
        return self.res

原文地址:https://www.cnblogs.com/seyjs/p/10084253.html

时间: 12-07

【leetcode】951. Flip Equivalent Binary Trees的相关文章

【LeetCode】 Maximum Depth of Binary Tree

Maximum Depth of Binary Tree  Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 递归基础,不解释. class Solution { public: int getMax(TreeNode *root

【leetcode】Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 利用递归. 也可以使用栈和队列,即使用DFS和BFS方法. C++: 1 /** 2 * Definition for binary tree 3 * struct TreeNod

【LeetCode】Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys

【LeetCode】Add Binary

Given two binary strings, return their sum (also a binary string). For example,a = "11"b = "1"Return "100". public class Solution { public String addBinary(String a, String b) { if(a.equalsIgnoreCase("")||a==null) r

【Leetcode】Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you do it iteratively? 思路:后序遍历比起先序遍历以及中序遍历要稍微复杂一点,可以考虑用两个stack进行操作,

【Leetcode】Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] 思路:使用

【Leetcode】Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / 15 7 return its bottom-up level order trave

【Leetcode】Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22, 5 / 4 8 / / 11 13 4 / \ / 7 2 5 1 return [ [5,4,11,2], [5,8,4,5] ] 思路:与[Leetcode]Path Sum 不同

【LeetCode】Search Insert Position (2 solutions)

Search Insert Position Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples.[1,3,5,

【leetcode】Generate Parentheses

题目: 给定整数n,返回n对匹配的小括号字符串数组. For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()" 分析: 这种问题的模式是:1)问题的解有多个 ,2)每个解都是由多个有效的 "步骤" 组成的,3)变更以有解的某个或某些"步骤"