📖
Go Leetcode
  • Welcome!
  • Golang
    • 1. Two Sum
    • 2. Add Two Numbers
    • 3. Longest Substring Without Repeating Characters
    • 5. Longest Palindromic Substring
    • 6. Zigzag Conversion
    • 14. Longest Common Prefix
    • 16. 3Sum Closest
    • 19. Remove Nth Node From End of List
    • 21. Merge Two Sorted Lists
    • 23. Merge k Sorted Lists
    • 24. Swap Nodes in Pairs
    • 26. Remove Duplicates from Sorted Array
    • 27. Remove Element
    • 28. Find the Index of the First Occurrence in a String
    • 32. Longest Valid Parentheses
    • 33. Search in Rotated Sorted Array
    • 34. Find First and Last Position of Element in Sorted Array
    • 35. Search Insert Position
    • 40. Combination Sum II
    • 45. Jump Game II
    • 46. Permutations ⭐
    • 47. Permutations II ⭐
    • 49. Group Anagrams
    • 53. Maximum Subarray
    • 55. Jump Game
    • 56. Merge Intervals
    • 54. Spiral Matrix
    • 57. Insert Interval
    • 58. Length of Last Word
    • 59. Spiral Matrix II ⭐
    • 63. Unique Paths II
    • 64. Minimum Path Sum
    • 69. Sqrt(x)
    • 70. Climbing Stairs
    • 72. Edit Distance
    • 74. Search a 2D Matrix
    • 75. Sort Colors
    • 78. Subsets
    • 79. Word Search
    • 80. Remove Duplicates from Sorted Array II
    • 81. Search in Rotated Sorted Array II ⭐
    • 82. Remove Duplicates from Sorted List II
    • 88. Merge Sorted Array
    • 90. Subsets II ⭐
    • 92. Reverse Linked List II
    • 94. Binary Tree Inorder Traversal
    • 96. Unique Binary Search Trees
    • 98. Validate Binary Search Tree ⭐
    • 102. Binary Tree Level Order Traversal
    • 103. Binary Tree Zigzag Level Order Traversal
    • 104. Maximum Depth of Binary Tree
    • 105. Construct Binary Tree from Preorder and Inorder Traversal
    • 106. Construct Binary Tree from Inorder and Postorder Traversal
    • 108. Convert Sorted Array to Binary Search Tree
    • 109. Convert Sorted List to Binary Search Tree ⭐
    • 110. Balanced Binary Tree ⭐
    • 111. Minimum Depth of Binary Tree
    • 112. Path Sum
    • 113. Path Sum II
    • 116. Populating Next Right Pointers in Each Node
    • 119. Pascal's Triangle II
    • 120. Triangle
    • 121. Best Time to Buy and Sell Stock
    • 122. Best Time to Buy and Sell Stock II
    • 124. Binary Tree Maximum Path Sum
    • 125. Valid Palindrome
    • 127. Word Ladder ⭐
    • 128. Longest Consecutive Sequence
    • 129. Sum Root to Leaf Numbers
    • 131. Palindrome Partitioning ⭐
    • 134. Gas Station
    • 142. Linked List Cycle II
    • 144. Binary Tree Preorder Traversal
    • 145. Binary Tree Postorder Traversal ⭐
    • 143. Reorder List
    • 144. Binary Tree Preorder Traversal ⭐
    • 147. Insertion Sort List
    • 148. Sort List
    • 150. Evaluate Reverse Polish Notation
    • 151. Reverse Words in a String
    • 152. Maximum Product Subarray
    • 153. Find Minimum in Rotated Sorted Array
    • 155. Min Stack
    • 160. Intersection of Two Linked Lists
    • 167. Two Sum II - Input Array Is Sorted
    • 173. Binary Search Tree Iterator
    • 175. Combine Two Tables
    • 182. Duplicate Emails
    • 183. Customers Who Never Order
    • 187. Repeated DNA Sequences
    • 190. Reverse Bits
    • 196. Delete Duplicate Emails
    • 198. House Robber
    • 199. Binary Tree Right Side View
    • 200. Number of Islands
    • 202. Happy Number
    • 205. Isomorphic Strings
    • 206. Reverse Linked List
    • 208. Implement Trie (Prefix Tree)
    • 209. Minimum Size Subarray Sum
    • 210. Course Schedule II
    • 211. Design Add and Search Words Data Structure
    • 213. House Robber II
    • 219. Contains Duplicate II
    • 221. Maximal Square
    • 225. Implement Stack using Queues
    • 226. Invert Binary Tree
    • 230. Kth Smallest Element in a BST
    • 234. Palindrome Linked List
    • 235. Lowest Common Ancestor of a Binary Search Tree
    • 237. Delete Node in a Linked List
    • 257. Binary Tree Paths
    • 258. Add Digits
    • 260. Single Number III
    • 263. Ugly Number
    • 264. Ugly Number II
    • 278. First Bad Version
    • 279. Perfect Squares
    • 290. Word Pattern
    • 229. Majority Element II
    • 299. Bulls and Cows
    • 303. Range Sum Query - Immutable
    • 316. Remove Duplicate Letters
    • 318. Maximum Product of Word Lengths
    • 322. Coin Change
    • 328. Odd Even Linked List
    • 331. Verify Preorder Serialization of a Binary Tree
    • 334. Increasing Triplet Subsequence
    • 342. Power of Four
    • 343. Integer Break
    • 345. Reverse Vowels of a String
    • 349. Intersection of Two Arrays
    • 350. Intersection of Two Arrays II
    • 367. Valid Perfect Square
    • 374. Guess Number Higher or Lower
    • 376. Wiggle Subsequence
    • 377. Combination Sum IV
    • 380. Insert Delete GetRandom O(1)
    • 382. Linked List Random Node
    • 383. Ransom Note
    • 384. Shuffle an Array
    • 387. First Unique Character in a String
    • 389. Find the Difference
    • 392. Is Subsequence
    • 394. Decode String ⭐
    • 398. Random Pick Index
    • 404. Sum of Left Leaves ⭐
    • 406. Queue Reconstruction by Height
    • 409. Longest Palindrome
    • 412. Fizz Buzz
    • 413. Arithmetic Slices ⭐
    • 414. Third Maximum Number
    • 415. Add Strings
    • 417. Pacific Atlantic Water Flow
    • 419. Battleships in a Board
    • 424. Longest Repeating Character Replacement
    • 427. Construct Quad Tree
    • 429. N-ary Tree Level Order Traversal
    • 430. Flatten a Multilevel Doubly Linked List
    • 433. Minimum Genetic Mutation
    • 438. Find All Anagrams in a String
    • 441. Arranging Coins
    • 442. Find All Duplicates in an Array
    • 445. Add Two Numbers II
    • 448. Find All Numbers Disappeared in an Array
    • 450. Delete Node in a BST
    • 451. Sort Characters By Frequency
    • 452. Minimum Number of Arrows to Burst Balloons
    • 453. Minimum Moves to Equal Array Elements
    • 459. Repeated Substring Pattern
    • 463. Island Perimeter
    • 485. Max Consecutive Ones
    • 491. Non-decreasing Subsequences ⭐
    • 492. Construct the Rectangle
    • 496. Next Greater Element I
    • 503. Next Greater Element II
    • 508. Most Frequent Subtree Sum
    • 513. Find Bottom Left Tree Value
    • 515. Find Largest Value in Each Tree Row
    • 516. Longest Palindromic Subsequence
    • 518. Coin Change II ⭐
    • 520. Detect Capital
    • 523. Continuous Subarray Sum ⭐
    • 525. Contiguous Array
    • 532. K-diff Pairs in an Array
    • 535. Encode and Decode TinyURL
    • 538. Convert BST to Greater Tree
    • 539. Minimum Time Difference
    • 540. Single Element in a Sorted Array ⭐
    • 543. Diameter of Binary Tree
    • 547. Number of Provinces
    • 551. Student Attendance Record I
    • 554. Brick Wall
    • 559. Maximum Depth of N-ary Tree
    • 560. Subarray Sum Equals K
    • 561. Array Partition
    • 566. Reshape the Matrix
    • 572. Subtree of Another Tree ⭐
    • 583. Delete Operation for Two Strings
    • 589. N-ary Tree Preorder Traversal
    • 590. N-ary Tree Postorder Traversal
    • 594. Longest Harmonious Subsequence
    • 599. Minimum Index Sum of Two Lists
    • 606. Construct String from Binary Tree
    • 623. Add One Row to Tree
    • 633. Sum of Square Numbers
    • 637. Average of Levels in Binary Tree
    • 643. Maximum Average Subarray I
    • 645. Set Mismatch
    • 646. Maximum Length of Pair Chain
    • 647. Palindromic Substrings
    • 648. Replace Words
    • 649. Dota2 Senate
    • 650. 2 Keys Keyboard
    • 652. Find Duplicate Subtrees
    • 653. Two Sum IV - Input is a BST
    • 654. Maximum Binary Tree
    • 657. Robot Return to Origin
    • 658. Find K Closest Elements
    • 662. Maximum Width of Binary Tree
    • 669. Trim a Binary Search Tree
    • 677. Map Sum Pairs
    • 678. Valid Parenthesis String
    • 684. Redundant Connection
    • 692. Top K Frequent Words
    • 693. Binary Number with Alternating Bits
    • 695. Max Area of Island
    • 701. Insert into a Binary Search Tree
    • 704. Binary Search
    • 714. Best Time to Buy and Sell Stock with Transaction Fee ⭐
    • 724. Find Pivot Index
    • 725. Split Linked List in Parts
    • 733. Flood Fill
    • 739. Daily Temperatures
    • 740. Delete and Earn
    • 743. Network Delay Time
    • 744. Find Smallest Letter Greater Than Target
    • 746. Min Cost Climbing Stairs
    • 766. Toeplitz Matrix
    • 769. Max Chunks To Make Sorted
    • 771. Jewels and Stones
    • 783. Minimum Distance Between BST Nodes
    • 785. Is Graph Bipartite? ⭐
    • 790. Domino and Tromino Tiling ⭐
    • 791. Custom Sort String
    • 792. Number of Matching Subsequences
    • 797. All Paths From Source to Target ⭐
    • 811. Subdomain Visit Count
    • 814. Binary Tree Pruning
    • 821. Shortest Distance to a Character
    • 830. Positions of Large Groups
    • 832. Flipping an Image
    • 835. Image Overlap
    • 836. Rectangle Overlap
    • 841. Keys and Rooms
    • 845. Longest Mountain in Array
    • 844. Backspace String Compare
    • 852. Peak Index in a Mountain Array
    • 865. Smallest Subtree with all the Deepest Nodes ⭐
    • 869. Reordered Power of 2
    • ⭐ 886. Possible Bipartition
    • 872. Leaf-Similar Trees
    • 873. Length of Longest Fibonacci Subsequence
    • 875. Koko Eating Bananas
    • 876. Middle of the Linked List
    • 881. Boats to Save People
    • 884. Uncommon Words from Two Sentences
    • 888. Fair Candy Swap
    • 889. Construct Binary Tree from Preorder and Postorder Traversal
    • 896. Monotonic Array
    • 897. Increasing Order Search Tree
    • 899. Orderly Queue
    • 901. Online Stock Span
    • 904. Fruit Into Baskets
    • 905. Sort Array By Parity
    • 908. Smallest Range I
    • 918. Maximum Sum Circular Subarray
    • 921. Minimum Add to Make Parentheses Valid
    • 926. Flip String to Monotone Increasing ⭐
    • 931. Minimum Falling Path Sum
    • 938. Range Sum of BST
    • 944. Delete Columns to Make Sorted
    • 946. Validate Stack Sequences
    • 951. Flip Equivalent Binary Trees
    • 953. Verifying an Alien Dictionary
    • 958. Check Completeness of a Binary Tree ⭐
    • 976. Largest Perimeter Triangle
    • 977. Squares of a Sorted Array
    • 978. Longest Turbulent Subarray
    • 979. Distribute Coins in Binary Tree ⭐
    • 988. Smallest String Starting From Leaf
    • 989. Add to Array-Form of Integer
    • 990. Satisfiability of Equality Equations ⭐
    • 993. Cousins in Binary Tree
    • 997. Find the Town Judge
    • 998. Maximum Binary Tree II
    • 1004. Max Consecutive Ones III
    • 1008. Construct Binary Search Tree from Preorder Traversal
    • 1014. Best Sightseeing Pair
    • 1022. Sum of Root To Leaf Binary Numbers
    • 1026. Maximum Difference Between Node and Ancestor
    • 1038. Binary Search Tree to Greater Sum Tree
    • 1047. Remove All Adjacent Duplicates In String
    • 1051. Height Checker
    • 1061. Lexicographically Smallest Equivalent String
    • 1071. Greatest Common Divisor of Strings
    • 1078. Occurrences After Bigram
    • 1079. Letter Tile Possibilities ⭐
    • 1089. Duplicate Zeros
    • 1110. Delete Nodes And Return ⭐ Forest
    • 1122. Relative Sort Array
    • 1129. Shortest Path with Alternating Colors ⭐
    • 1137. N-th Tribonacci Number
    • 1143. Longest Common Subsequence
    • 1161. Maximum Level Sum of a Binary Tree
    • 1162. As Far from Land as Possible ⭐
    • 1207. Unique Number of Occurrences
    • 1218. Longest Arithmetic Subsequence of Given Difference
    • 1219. Path with Maximum Gold
    • 1254. Number of Closed Islands ⭐
    • 1261. Find Elements in a Contaminated Binary Tree
    • 1267. Count Servers that Communicate
    • 1268. Search Suggestions System
    • 1286. Iterator for Combination
    • 1295. Find Numbers with Even Number of Digits
    • 1299. Replace Elements with Greatest Element on Right Side
    • 1302. Deepest Leaves Sum
    • 1304. Find N Unique Integers Sum up to Zero
    • 1305. All Elements in Two Binary Search Trees
    • 1306. Jump Game III
    • 1315. Sum of Nodes with Even-Valued Grandparent
    • 1319. Number of Operations to Make Network Connected ⭐
    • 1323. Maximum 69 Number
    • 1325. Delete Leaves With a Given Value
    • 1328. Break a Palindrome
    • 1331. Rank Transform of an Array
    • 1335. Minimum Difficulty of a Job Schedule
    • 1337. The K Weakest Rows in a Matrix
    • 1339. Maximum Product of Splitted Binary Tree ⭐
    • 1345. Jump Game IV
    • 1346. Check If N and Its Double Exist
    • 1347. Minimum Number of Steps to Make Two Strings Anagram
    • 1351. Count Negative Numbers in a Sorted Matrix
    • 1358. Number of Substrings Containing All Three Characters
    • 1372. Longest ZigZag Path in a Binary Tree ⭐
    • 1376. Time Needed to Inform All Employees
    • 1382. Balance a Binary Search Tree
    • 1385. Find the Distance Value Between Two Arrays
    • 1394. Find Lucky Integer in an Array
    • 1395. Count Number of Teams
    • 1402. Reducing Dishes
    • 1408. String Matching in an Array
    • 1417. Reformat The String
    • 1443. Minimum Time to Collect All Apples in a Tree
    • 1448. Count Good Nodes in Binary Tree
    • 1450. Number of Students Doing Homework at a Given Time
    • 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence
    • 1456. Maximum Number of Vowels in a Substring of Given Length
    • 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
    • 1466. Reorder Routes to Make All Paths Lead to the City Zero
    • 1470. Shuffle the Array
    • 1472. Design Browser History
    • 1480. Running Sum of 1d Array
    • 1491. Average Salary Excluding the Minimum and Maximum Salary
    • 1493. Longest Subarray of 1's After Deleting One Element ⭐
    • 1496. Path Crossing
    • 1497. Check If Array Pairs Are Divisible by k
    • 1498. Number of Subsequences That Satisfy the Given Sum Condition
    • 1502. Can Make Arithmetic Progression From Sequence
    • 1507. Reformat Date
    • 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
    • 1512. Number of Good Pairs
    • 1518. Water Bottles
    • 1519. Number of Nodes in the Sub-Tree With the Same Label ⭐
    • 1523. Count Odd Numbers in an Interval Range
    • 1539. Kth Missing Positive Number
    • 1557. Minimum Number of Vertices to Reach All Nodes
    • 1608. Special Array With X Elements Greater Than or Equal X
    • 1941. Check if All Characters Have Equal Number of Occurrences
    • 1544. Make The String Great
    • 1550. Three Consecutive Odds
    • 1556. Thousand Separator
    • 1567. Maximum Length of Subarray With Positive Product ⭐
    • 1572. Matrix Diagonal Sum
    • 1576. Replace All ?'s to Avoid Consecutive Repeating Characters
    • 1578. Minimum Time to Make Rope Colorful
    • 1588. Sum of All Odd Length Subarrays
    • 1636. Sort Array by Increasing Frequency
    • 1657. Determine if Two Strings Are Close
    • 1662. Check If Two String Arrays are Equivalent
    • 1669. Merge In Between Linked Lists
    • 1704. Determine if String Halves Are Alike
    • 1706. Where Will the Ball Fall
    • 1710. Maximum Units on a Truck
    • 1716. Calculate Money in Leetcode Bank
    • 1720. Decode XORed Array
    • 1732. Find the Highest Altitude
    • 1734. Decode XORed Permutation
    • 1748. Sum of Unique Elements
    • 1764. Form Array by Concatenating Subarrays of Another Array
    • 1765. Map of Highest Peak
    • 1768. Merge Strings Alternately
    • 1773. Count Items Matching a Rule
    • 1781. Sum of Beauty of All Substrings
    • 1791. Find Center of Star Graph
    • 1822. Sign of the Product of an Array
    • 1832. Check if the Sentence Is Pangram
    • 1833. Maximum Ice Cream Bars
    • 1863. Sum of All Subset XOR Totals
    • 1905. Count Sub Islands
    • 1913. Maximum Product Difference Between Two Pairs
    • 1945. Sum of Digits of String After Convert
    • 1952. Three Divisors
    • 1962. Remove Stones to Minimize the Total
    • 1974. Minimum Time to Type Word Using Special Typewriter
    • 1979. Find Greatest Common Divisor of Array
    • 1980. Find Unique Binary String
    • 1992. Find All Groups of Farmland
    • 2024. Maximize the Confusion of an Exam
    • 2044. Count Number of Maximum Bitwise-OR Subsets
    • 2090. K Radius Subarray Averages
    • 2091. Removing Minimum and Maximum From Array
    • 2095. Delete the Middle Node of a Linked List
    • 2116. Check if a Parentheses String Can Be Valid
    • 2129. Capitalize the Title
    • 2130. Maximum Twin Sum of a Linked List
    • 2131. Longest Palindrome by Concatenating Two Letter Words
    • 2133. Check if Every Row and Column Contains All Numbers
    • 2144. Minimum Cost of Buying Candies With Discount
    • 2180. Count Integers With Even Digit Sum
    • 2181. Merge Nodes in Between Zeros
    • 2185. Counting Words With a Given Prefix
    • 2186. Minimum Number of Steps to Make Two Strings Anagram II
    • 2191. Sort the Jumbled Numbers
    • 2196. Create Binary Tree From Descriptions
    • 2215. Find the Difference of Two Arrays
    • 2225. Find Players With Zero or One Losses
    • 2235. Add Two Integers
    • 2236. Root Equals Sum of Children
    • 2239. Find Closest Number to Zero
    • 2244. Minimum Rounds to Complete All Tasks
    • 2248. Intersection of Multiple Arrays
    • 2255. Count Prefixes of a Given String
    • 2256. Minimum Average Difference
    • 2257. Count Unguarded Cells in the Grid
    • 2259. Remove Digit From Number to Maximize Result
    • 2260. Minimum Consecutive Cards to Pick Up
    • 2264. Largest 3-Same-Digit Number in String
    • 2265. Count Nodes Equal to Average of Subtree ⭐
    • 2269. Find the K-Beauty of a Number
    • 2273. Find Resultant Array After Removing Anagrams
    • 2278. Percentage of Letter in String
    • 2279. Maximum Bags With Full Capacity of Rocks
    • 2283. Check if Number Has Equal Digit Count and Digit Value
    • 2287. Rearrange Characters to Make Target String
    • 2293. Min Max Game
    • 2305. Fair Distribution of Cookies ⭐
    • 2316. Count Unreachable Pairs of Nodes in an Undirected Graph
    • 2328. Number of Increasing Paths in a Grid
    • 2331. Evaluate Boolean Binary Tree
    • 2336. Smallest Number in Infinite Set
    • 2348. Number of Zero-Filled Subarrays
    • 2351. First Letter to Appear Twice
    • 2352. Equal Row and Column Pairs
    • 2359. Find Closest Node to Given Two Nodes
    • 2364. Count Number of Bad Pairs
    • 2375. Construct Smallest Number From DI String
    • 2389. Longest Subsequence With Limited Sum
    • 2390. Removing Stars From a String
    • 2391. Minimum Amount of Time to Collect Garbage
    • 2396. Strictly Palindromic Number
    • 2404. Most Frequent Even Element
    • 2405. Optimal Partition of String
    • 2410. Maximum Matching of Players With Trainers
    • 2413. Smallest Even Multiple
    • 2418. Sort the People
    • 2419. Longest Subarray With Maximum Bitwise AND
    • 2428. Maximum Sum of an Hourglass
    • 2441. Largest Positive Integer That Exists With Its Negative
    • 2442. Count Number of Distinct Integers After Reverse Operations
    • 2452. Words Within Two Edits of Dictionary
    • 2460. Apply Operations to an Array
    • 2461. Maximum Sum of Distinct Subarrays With Length K
    • 2465. Number of Distinct Averages
    • 2477. Minimum Fuel Cost to Report to the Capital ⭐
    • 2481. Minimum Cuts to Divide a Circle
    • 2486. Append Characters to String to Make Subsequence
    • 2487. Remove Nodes From Linked List
    • 2491. Divide Players Into Teams of Equal Skill
    • 2492. Minimum Score of a Path Between Two Cities
    • 2496. Maximum Value of a String in an Array
    • 2500. Delete Greatest Value in Each Row
    • 2574. Left and Right Sum Differences
    • 2602. Minimum Operations to Make All Array Elements Equal
    • 2658. Maximum Number of Fish in a Grid
    • 3065. Minimum Operations to Exceed Threshold Value I
    • 509. Fibonacci Number
Powered by GitBook
On this page
  1. Golang

951. Flip Equivalent Binary Trees

Medium

Previous946. Validate Stack SequencesNext953. Verifying an Alien Dictionary

Last updated 2 years ago

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.

Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.

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.

Example 2:

Input: root1 = [], root2 = []
Output: true

Example 3:

Input: root1 = [], root2 = [1]
Output: false

Constraints:

  • The number of nodes in each tree is in the range [0, 100].

  • Each tree will have unique node values in the range [0, 99].

解題

Runtime: 0 ms, faster than 100%

Memory Usage: 2.4 MB, less than 77.78%

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
    if root1 == nil && root2 == nil { // 兩個都nil,相等,回傳true
        return true
    }

    if root1 == nil || root2 == nil || root1.Val != root2.Val { 
        // 只有一邊nil或root值不相等,樹必然不相同,回傳false,
        return false
    } 
    
    return (flipEquiv(root1.Left, root2.Left) && flipEquiv(root1.Right, root2.Right)) || (flipEquiv(root1.Left, root2.Right) && flipEquiv(root1.Right, root2.Left))
    // 不用交換樹就相同 || 交換後樹變相同
}
Flipped Trees Diagram