226. Invert Binary Tree

week 1 number 6

مسئله: معکوس کردن درخت دودویی (Invert Binary Tree)

فرضیه: ریشه یک درخت دودویی به شما داده شده است. وظیفه شما این است که درخت را معکوس کنید و ریشه معکوس شده را برگردانید.

معکوس کردن درخت دودویی: به این معنی است که جای زیر درخت چپ و راست هر گره را با هم عوض کنید.

مثال:

     1
    / \
   2   3
  / \  / \
 4   5 6   7

درخت معکوس شده:

     1
    / \
   3   2
  / \  / \
 7   6 5   4

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

محدودیت‌ها:

• تعداد گره‌ها در درخت بین ۰ تا ۱۰۰ قرار دارد.
• ۱۰۰- <= مقدار گره <= ۱۰۰

راه‌حل ۱: بازگشت (Recursion)

ایده بازگشت/recursion بسیار ساده است. زیر درخت چپ و راست گره فعلی را جابه‌جا می‌کنیم و سپس به طور بازگشتی زیر درخت چپ و راست گره فعلی را جابه‌جا می‌کنیم.

پیچیدگی زمانی: O(n) که در آن n تعداد گره‌های درخت دودویی است.

پیچیدگی فضایی: O(n) که در آن n ارتفاع درخت دودویی است (در بدترین حالت، زمانی که درخت یک زنجیره است، برابر با n می‌شود).

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
 var dfs func(*TreeNode)
 dfs = func(root *TreeNode) {
  if root == nil {
   return
  }
  root.Left, root.Right = root.Right, root.Left
  dfs(root.Left)
  dfs(root.Right)
 }
 dfs(root)
 return root
}

راه‌حل ۲:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
 if root == nil {
  return root
 }
 l, r := invertTree(root.Left), invertTree(root.Right)
 root.Left, root.Right = r, l
 return root
}