LeetCode 226. 翻转二叉树

• 题目：
  翻转一棵二叉树。

示例：

输入：

 4

/
2 7
/ \ /
1 3 6 9

输出：

 4

/
7 2
/ \ /
9 6 3 1

• 解题思路
  1.递归法
  递归出口：到叶子节点，则返回
  否则，交换左右子树
  代码实现（C++)

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

2非递归实现
类似于层次遍历
代码实现

 TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> tree_queue;
        if(root == nullptr)
            return root;
       // TreeNode* cur = root;
        tree_queue.push(root);             //根节点入队
        while(!tree_queue.empty())       //队列不空时执行循环
        {
            TreeNode* cur = tree_queue.front();          //对头节点
            tree_queue.pop();                             //出队
            TreeNode *temp = cur->left;
            cur->left = cur->right;
            cur->right = temp;
            if(cur->left)
                tree_queue.push(cur->left);
            if(cur->right)
                tree_queue.push(cur->right);
        }
        return root;
    }