【LeetCode】#226 Invert Binary Tree

Invert a binary tree.

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

1
2
3
4
5

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

to

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

1
2
3
4
5

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

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

题目大意，要求翻转一棵二叉树。最后一句是说Homebrew软件的作者面试谷歌时，谷歌：我们90%的工程师都在使用你写的软件，然而你却不会翻转一棵二叉树，所以，去你妹的吧。

（1）递归的对每个节点交换其左右孩子节点即可
解法一

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root)
            return root;

        TreeNode *temp;
        temp = invertTree(root->left);
        root->left = invertTree(root->right);
        root->right = temp
        
        return root;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

TreeNode* invertTree(TreeNode* root) {

if (!root)

return root;

TreeNode *temp;

temp = invertTree(root->left);

root->left = invertTree(root->right);

root->right = temp

return root;

}

};

（2）非递归的求解，遍历二叉树。可以使用队列queue(先进先出)：若root非空，则将root节点push到queue中，交换其左右孩子节点；取出root节点，再将其左右孩子节点push到queue中，然后处理左右孩子节点…直到队列中没有元素。

解法二

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> queueNode;
        TreeNode *curNode, *temp;
    
        if (root)
             queueNode.push(root);
        while (!queueNode.empty()) {
            curNode = queueNode.front();
            queueNode.pop();
            temp = curNode->left;
            curNode->left = curNode->right;
            curNode->right = temp;
        
            if(curNode->left) queueNode.push(curNode->left);
            if(curNode->right) queueNode.push(curNode->right);
        }
        return root;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

TreeNode* invertTree(TreeNode* root) {

queue<TreeNode*> queueNode;

TreeNode *curNode, *temp;

if (root)

queueNode.push(root);

while (!queueNode.empty()) {

curNode = queueNode.front();

queueNode.pop();

temp = curNode->left;

curNode->left = curNode->right;

curNode->right = temp;

if(curNode->left) queueNode.push(curNode->left);

if(curNode->right) queueNode.push(curNode->right);

}

return root;

}

};

（3）上述（2）中使用queue先进先出的特点，将节点push到队列中后，先push进去的节点被先处理（交换其左右孩子节点）并pop出来。
其实也可以使用其他的数据结构，比如vector。因为这里“先进先出”的特性不是必须的。只要保证每个节点都被“处理”过且只被“处理”一次就可以。

解法三

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        vector<TreeNode*> vectorNode;
        TreeNode *curNode;
        if (root)
            vectorNode.push_back(root);
        while (!vectorNode.empty()) {
            curNode = vectorNode.back();
            vectorNode.pop_back();
            swap(curNode->left, curNode->right);
            
            if (curNode->left) vectorNode.push_back(curNode->left);
            if (curNode->right) vectorNode.push_back(curNode->right);
        }
        return root;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

TreeNode* invertTree(TreeNode* root) {

vector<TreeNode*> vectorNode;

TreeNode *curNode;

if (root)

vectorNode.push_back(root);

while (!vectorNode.empty()) {

curNode = vectorNode.back();

vectorNode.pop_back();

swap(curNode->left, curNode->right);

if (curNode->left) vectorNode.push_back(curNode->left);

if (curNode->right) vectorNode.push_back(curNode->right);

}

return root;

}

};

附：
（1）queue是一个先进先出的数据结构，即从尾端进去（ queue.push() ），首端出来（ queue.pop() ）。注意，不存在queue.push_back()以及queue.pop_front()。
（2）而vector数据结构是一个线性存储的容器，其push和pop操作都是在容器的尾端进行的：vector.push_back()、vector.pop_back()。注意，不存在vector.push_front()和vector.pop_front()。

有关STL容器的内容，可参考其它相关博文。

发表评论 取消回复

发表评论取消回复