Invert Binary Tree

Question

  1. Invert a binary tree.
  3. Example
  4.   1         1
  5.  / \       / \
  6. 2   3  => 3   2
  7.    /       \
  8.   4         4
  9. Challenge
  10. Do it in recursion is acceptable, can you do it without recursion?

題解1 - Recursive

二元樹的題用遞迴的思想求解自然是最容易的，此題要求爲交換左右子節點，故遞迴交換即可。具體實現可分返回值爲NULL或者二元樹節點兩種情況，返回值爲節點的情況理解起來相對不那麼直觀一些。

C++ - return void

  1. /**
  2.  * Definition of TreeNode:
  3.  * class TreeNode {
  4.  * public:
  5.  *     int val;
  6.  *     TreeNode *left, *right;
  7.  *     TreeNode(int val) {
  8.  *         this->val = val;
  9.  *         this->left = this->right = NULL;
  10.  *     }
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param root: a TreeNode, the root of the binary tree
  17.      * @return: nothing
  18.      */
  19.     void invertBinaryTree(TreeNode *root) {
  20.         if (root == NULL) return;
  21.         swap(root->left, root->right);
  22.         invertBinaryTree(root->left);
  23.         invertBinaryTree(root->right);
  24.     }
  25. };

C++ - return TreeNode *

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     TreeNode* invertTree(TreeNode* root) {
  13.         if (root == NULL) return NULL;
  15.         TreeNode *temp = root->left;
  16.         root->left = invertTree(root->right);
  17.         root->right = invertTree(temp);
  19.         return root;
  20.     }
  21. };

源碼分析

分三塊實現，首先是節點爲空的情況，然後交換左右節點，最後遞迴調用，遞迴調用的正確性可通過畫圖理解。

複雜度分析

每個節點遍歷一次，時間複雜度爲 O(n), 使用了臨時變數，空間複雜度爲 O(1).

題解2 - Iterative

遞迴的實現非常簡單，那麼非遞迴的如何實現呢？如果將遞迴改寫成 stack 的實現，那麼簡單來講就需要兩個 stack 了，稍顯複雜。其實仔細觀察此題可發現使用 level-order 的遍歷次序也可實現。即從根節點開始進入隊列 queue，交換左右節點，並將非空的左右子節點進入隊列，從隊列中取出節點，交換之，直至隊列爲空。

C++

  1. /**
  2.  * Definition of TreeNode:
  3.  * class TreeNode {
  4.  * public:
  5.  *     int val;
  6.  *     TreeNode *left, *right;
  7.  *     TreeNode(int val) {
  8.  *         this->val = val;
  9.  *         this->left = this->right = NULL;
  10.  *     }
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param root: a TreeNode, the root of the binary tree
  17.      * @return: nothing
  18.      */
  19.     void invertBinaryTree(TreeNode *root) {
  20.         if (root == NULL) return;
  22.         queue<TreeNode*> q;
  23.         q.push(root);
  24.         while (!q.empty()) {
  25.             // pop out the front node
  26.             TreeNode *node = q.front();
  27.             q.pop();
  28.             // swap between left and right pointer
  29.             swap(node->left, node->right);
  30.             // push non-NULL node
  31.             if (node->left != NULL) q.push(node->left);
  32.             if (node->right != NULL) q.push(node->right);
  33.         }
  34.     }
  35. };

源碼分析

交換左右指針後需要判斷子節點是否非空，僅入隊非空子節點。

複雜度分析

遍歷每一個節點，時間複雜度爲 O(n), 使用了隊列，最多存儲最下一層子節點數目，最多只有總節點數的一半，故最壞情況下 O(n).

Reference