刷題日記（11）Invert Binary Tree

Invert a binary tree.

Example:

Input:

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

Output:

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

— — — — — --— (解法1, 用遞迴來解) — — — — -— — —

解題思路：

設定base case，遞歸出口，當root==null時，代表沒有節點了return null

左右子樹先交換

開始遞迴

(main function)

1. 當root等於null時，return null，遞歸到最下面的node時，等於null，return null
2. 設一個tmp node開始交換，交換root的左右子樹的位置
3. 接著把左子樹傳給invertTree就是呼叫自己這個function開始遞迴
4. 開始處理左孫子和右孫子的交換，交換完之後，繼續遞迴左孫子的左孩子
5. 左孫子的左孩子和右孩子都為null，交換完之後再一次遞迴會遇到base case return null
6. 接著完成那層的遞迴後return root，可是沒有變數node接住它，這裡的return 沒有用
7. 一樣處理右子樹的左孫子右孫子和他們的孩子們
8. 最後右子樹一樣return root給root那層遞迴，但是沒有變數node接住它，所以依舊沒有用
9. 最後樹下方的左子樹和右子樹遞迴全部完成後
10. return root，這次這個root就是答案了，root沒有變，root傳回去會得到反轉完成的一棵樹

— — — — —(解法2, 用寬度優先遍歷queue來解) — — — — - —

解題思路：

新增一個queue，把root放進去

當queue不會空時，交換，然後加入cur的left和right進隊列

queue為空時，回傳root

(mainfunction)

1. 設定base case如果root等於null，回傳null

2. 新建一個空的queue

3. 把樹的root加入queue

4. while (queue不是空時)，queue poll出來一個，幫他加上變數標籤為cur

4.1 然後再新增一個TreeNode (0)叫tmp

4.2 開始交換，把cur.left的值給tmp，然後把cur.right的值給cur.left，最後再把tmp一開始接到的值給cur.right，完成了交換

5.如果cur.left不為null時，就把cur.left加到queue裡，排隊等待下一次交換

6.如果cur.right不為null時，就把cur.right加到queue裡，排隊等待下一次交換

7.迴圈結束後，queue為空時，回傳root，代表queue裡面的都已經交換過了