LeetCode:Invert Binary Tree

Invert a binary tree.

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

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

解題思路：類似於後序遍歷的思想，遞歸的思想，先完成左子樹的交換，再完成右子樹的交換，再將根節點的左右子樹交換。

未優化代碼如下：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
     if(root==NULL) return NULL;//當樹為一顆空樹的時候。
     if(root->left||root->right){//當節點的左右子樹至少有一個不為空的時候，必須遞歸進行交換。
         TreeNode *node=invertTree(root->left);
         root->left=invertTree(root->right);
         root->right=node;
         return root;
     }else{//當該節點左右子樹都為空的時候，沒有必要交換，直接返回該節點。
         return root;
     }
    }
};

之後觀看代碼可以發現，if-else語句中都有return root;區別在於if語句中對左右子樹進行了交換，而else語句中由於左右子樹都為空，沒有進行交換。

這裡，我們可以優化，認為else語句中兩棵空子樹也進行了交換，這樣就可以將if-else語句合並。

優化代碼如下：

    TreeNode* invertTree_recursive(TreeNode* root) {
        if (root==NULL) return root;
        TreeNode* node = invertTree_recursive(root->left);
        root->left = invertTree_recursive(root->right);
        root->right = node;
        return root;
    }

版權聲明：本文為博主原創文章，未經博主允許不得轉載。