翻转一棵二叉树。

  1. 输入：                    
  2.      4                
  3.    /   \                 
  4.   2     7                
  5.  / \   / \                      
  6. 1   3 6   9     
  7. 输出：
  8.      4
  9.    /   \
  10.   7     2
  11.  / \   / \
  12. 9   6 3   1

c plus

  • 递归
    实质就是遍历二叉树，然后交换左右子树
    题解

    1. class Solution {
    2. public:
    3.   TreeNode* invertTree(TreeNode* root) {
    4.       if (root == NULL) return NULL;
    5.       TreeNode *right = invertTree(root->right); //后序遍历，前序遍历先交换节点
    6.       TreeNode *left = invertTree(root->left);  
    7.       root->left = right;
    8.       root->right = left;
    9.       return root;
    10.   }
    11. };

  • 迭代
    类似于广度优先遍历，层层扫荡，需要队列或栈来存储数据。
    我们需要先将根节点放入到队列中，然后不断的迭代队列中的元素。
    对当前元素调换其左右子树的位置，然后：
    判断其左子树是否为空，不为空就放入队列中
    判断其右子树是否为空，不为空就放入队列中

    1. class Solution {
    2. public:
    3.   TreeNode* invertTree(TreeNode* root) {
    4.       if(root==NULL) return NULL;
    5.       queue<TreeNode *> q;
    6.       q.push(root);
    7.       while (!q.empty()) {
    8.           TreeNode *pre = q.front(); q.pop();
    9.           TreeNode *tmp = pre->left;
    10.           pre->left = pre->right;
    11.           pre->right = tmp;
    12.           if (pre->left != NULL)   q.push(pre->left);
    13.           if (pre->right != NULL)  q.push(pre->right);
    14.       } 
    15.       return root;
    16.   }
    17. };

%E7%BF%BB%E8%BD%AC%E4%B8%80%E6%A3%B5%E4%BA%8C%E5%8F%89%E6%A0%91%E3%80%82%0A%60%60%60%0A%E8%BE%93%E5%85%A5%EF%BC%9A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%204%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%2F%20%20%20%5C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%202%20%20%20%20%207%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%2F%20%5C%20%20%20%2F%20%5C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A1%20%20%203%206%20%20%209%20%20%20%20%20%0A%0A%E8%BE%93%E5%87%BA%EF%BC%9A%0A%20%20%20%20%204%0A%20%20%20%2F%20%20%20%5C%0A%20%207%20%20%20%20%202%0A%20%2F%20%5C%20%20%20%2F%20%5C%0A9%20%20%206%203%20%20%201%0A%60%60%60%0A%0A%23%23%23%20c%20plus%0A%0A%0A%20%E9%80%92%E5%BD%92%20%0A%20%20%20%E5%AE%9E%E8%B4%A8%E5%B0%B1%E6%98%AF%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%8C%E7%84%B6%E5%90%8E%E4%BA%A4%E6%8D%A2%E5%B7%A6%E5%8F%B3%E5%AD%90%E6%A0%91%0A%20%20%20%0A%20%20%20%20%5B%E9%A2%98%E8%A7%A3%5D(https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Finvert-binary-tree%2Fsolution%2Fdong-hua-yan-shi-liang-chong-shi-xian-226-fan-zhua%2F)%0A%60%60%60c%0Aclass%20Solution%20%7B%0Apublic%3A%0A%20%20%20%20TreeNode%20invertTree(TreeNode%20root)%20%7B%0A%20%20%20%20%20%20%20%20if%20(root%20%3D%3D%20NULL)%20return%20NULL%3B%0A%20%20%20%20%20%20%20%20TreeNode%20right%20%3D%20invertTree(root-%3Eright)%3B%20%2F%2F%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%EF%BC%8C%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86%E5%85%88%E4%BA%A4%E6%8D%A2%E8%8A%82%E7%82%B9%0A%20%20%20%20%20%20%20%20TreeNode%20left%20%3D%20invertTree(root-%3Eleft)%3B%20%20%0A%20%20%20%20%20%20%20%20root-%3Eleft%20%3D%20right%3B%0A%20%20%20%20%20%20%20%20root-%3Eright%20%3D%20left%3B%0A%20%20%20%20%20%20%20%20return%20root%3B%0A%20%20%20%20%7D%0A%7D%3B%0A%60%60%60%0A%0A*%20%E8%BF%AD%E4%BB%A3%0A%E7%B1%BB%E4%BC%BC%E4%BA%8E%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86%EF%BC%8C%E5%B1%82%E5%B1%82%E6%89%AB%E8%8D%A1%EF%BC%8C%E9%9C%80%E8%A6%81%E9%98%9F%E5%88%97%E6%88%96%E6%A0%88%E6%9D%A5%E5%AD%98%E5%82%A8%E6%95%B0%E6%8D%AE%E3%80%82%0A%E6%88%91%E4%BB%AC%E9%9C%80%E8%A6%81%E5%85%88%E5%B0%86%E6%A0%B9%E8%8A%82%E7%82%B9%E6%94%BE%E5%85%A5%E5%88%B0%E9%98%9F%E5%88%97%E4%B8%AD%EF%BC%8C%E7%84%B6%E5%90%8E%E4%B8%8D%E6%96%AD%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%98%9F%E5%88%97%E4%B8%AD%E7%9A%84%E5%85%83%E7%B4%A0%E3%80%82%0A%E5%AF%B9%E5%BD%93%E5%89%8D%E5%85%83%E7%B4%A0%E8%B0%83%E6%8D%A2%E5%85%B6%E5%B7%A6%E5%8F%B3%E5%AD%90%E6%A0%91%E7%9A%84%E4%BD%8D%E7%BD%AE%EF%BC%8C%E7%84%B6%E5%90%8E%EF%BC%9A%0A%E5%88%A4%E6%96%AD%E5%85%B6%E5%B7%A6%E5%AD%90%E6%A0%91%E6%98%AF%E5%90%A6%E4%B8%BA%E7%A9%BA%EF%BC%8C%E4%B8%8D%E4%B8%BA%E7%A9%BA%E5%B0%B1%E6%94%BE%E5%85%A5%E9%98%9F%E5%88%97%E4%B8%AD%0A%E5%88%A4%E6%96%AD%E5%85%B6%E5%8F%B3%E5%AD%90%E6%A0%91%E6%98%AF%E5%90%A6%E4%B8%BA%E7%A9%BA%EF%BC%8C%E4%B8%8D%E4%B8%BA%E7%A9%BA%E5%B0%B1%E6%94%BE%E5%85%A5%E9%98%9F%E5%88%97%E4%B8%AD%0A%60%60%60c%0Aclass%20Solution%20%7B%0Apublic%3A%0A%20%20%20%20TreeNode%20invertTree(TreeNode%20root)%20%7B%0A%20%20%20%20%20%20%20%20if(root%3D%3DNULL)%20return%20NULL%3B%0A%20%20%20%20%20%20%20%20queue%3CTreeNode%20%3E%20q%3B%0A%20%20%20%20%20%20%20%20q.push(root)%3B%0A%20%20%20%20%20%20%20%20while%20(!q.empty())%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20TreeNode%20pre%20%3D%20q.front()%3B%20q.pop()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20TreeNode%20tmp%20%3D%20pre-%3Eleft%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20pre-%3Eleft%20%3D%20pre-%3Eright%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20pre-%3Eright%20%3D%20tmp%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(pre-%3Eleft%20!%3D%20NULL)%20%20%20q.push(pre-%3Eleft)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(pre-%3Eright%20!%3D%20NULL)%20%20q.push(pre-%3Eright)%3B%0A%20%20%20%20%20%20%20%20%7D%20%0A%20%20%20%20%20%20%20%20return%20root%3B%0A%20%20%20%20%7D%0A%7D%3B%0A%60%60%60%0A%0A