LeetCode 226. Invert Binary Tree

題目

Invert a binary tree.

翻譯

反轉一個二元樹。

範例：
輸入

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

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

思路

第一次解這題的時候還跟遞迴不怎麼熟，一直用迴圈嘗試，結果也沒寫出來，那時候心中的不斷的OS，不是說好這是Easy的題目嗎!!!?

後來看討論發現用遞迴來解會比較好理解很多，如果你現在心中跟我有一樣的OS，那建議過幾周後再回來重寫一次。

反轉整顆樹，其實除了已經到底的節點(left)之外，毎一個節點都需要把他的左右節點互換，例如上面的[4, left:2, right:7]，就要把2，7互換， [2, left:1, right:3]，[7, left:6, right:9]也都是一樣，到了底部[1,3,6,9]這幾個點就不用交換，表示遞迴結束。

解題

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    //節點為null或沒有子節點，不用反轉，終止遞迴
    if(root === null || (root.right === null && root.left === null)){
        return root;    
    }
    // 左節點為本來的右節點反轉，右節點為本來的左節點反轉
    var temp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(temp);

    return root;

};

* 以[4][2,7][1,3,6,9]這個樹來說明
* 執行時傳入節點4，發現有左節點[2]，右節點[7]，將[2][7]交換
* 交換同時發現新的左節點[7]有子節點[9,6]，交換成為[6,9]，因為[6][9]都沒子節點，遞迴結束
* 接著看新的右節點[2]，有子節點[1,3]，步驟同上
* 上述步驟執行後就會得到反轉的tree [4][7,2][9,6,3,1]