目录

题目

递归写法

读者可能出现的错误写法

正确写法 

非递归写法

思路 

正确写法

---

题目

226. 翻转二叉树 - 力扣（LeetCode）

递归写法

读者可能出现的错误写法

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)
        {
            return;
        }

        TreeNode* Tleft = invertTree(root->left);
        TreeNode* Tright = invertTree(root->right);

        root->left = Tright;
        root->right = Tleft;
    }
};

返回类型不匹配：函数声明返回类型是TreeNode*，但在if(!root)条件中返回的是return;（无返回值）

应该返回nullptr表示空树，这样当递归到叶子节点之外时，可以正确地返回空指针给上一层调用。

正确写法 

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)
        {
            return nullptr;
        }

        TreeNode* Tleft = invertTree(root->left);
        TreeNode* Tright = invertTree(root->right);

        root->left = Tright;
        root->right = Tleft;

        return root;
    }
};

非递归写法

思路 

创建一个栈，将根节点入栈

当栈不为空时，弹出栈顶节点

交换该节点的左右子树

将该节点的非空子节点压入栈中

重复步骤2-4直到栈为空

这种方法的优点是避免了递归调用的栈开销，特别是对于非常深的树，可以避免栈溢出的风险。时间复杂度仍然是O(n)，其中n是树中节点的数量，因为每个节点只会被处理一次。

正确写法

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)
        {
            return nullptr;
        }

        stack<TreeNode*> st;
        st.push(root);

        while(!st.empty())
        {
            TreeNode* node = st.top();
            st.pop();

            TreeNode* tmp = node->left;
            node->left = node->right;
            node->right = tmp;

            if(node->right)
            {
                st.push(node->right);
            }

            if(node->left)
            {
                st.push(node->left);
            } 
        }

        return root;
    }
};