将每个结点的左右子树进行交换

  • 递归法
    • 前序
    • 中序：会将某些结点的左右子树翻转两次
    • 后序
    • 层序
  • 迭代法
    • 前序
    • 中序：避免了递归法的翻转多次情况，因为迭代法是靠栈来遍历，而不是靠指针来遍历，是先将当前结点的左右子结点存储在栈中，翻转后不会改变栈中左右子树的先后顺序
    • 后序
    • 层序

递归法

  • 前序遍历

    1. // 1 确定递归函数的参数和返回值
    2. TreeNode *invertTree(TreeNode *root) {
    3.   // 2 确定递归终止的条件
    4.   if (root == NULL) return root;
    5.   // 3 确定单层递归的逻辑
    6.   swap(root->left, root->right);  // 中
    7.   invertTree(root->left);  // 左
    8.   invertTree(root->right);  // 右
    9.   return root;
    10. }

  • 中序遍历 - 改进

    1. TreeNode *invertTree(TreeNode *root) {
    2.   // 2 确定递归终止的条件
    3.   if (root == NULL) return root;
    4.   // 3 确定单层递归的逻辑
    5.   invertTree(root->left);  // 左
    6.   swap(root->left, root->right);  // 中-翻转
    7.   invertTree(root->left);  // 左
    8.   return root;
    9. }

迭代法

模拟深度优先遍历

  • 前序遍历

    1. TreeNode *invertTree(TreeNode *root) {
    2.   if (root == NULL) return NULL;
    3.   stack<TreeNode *> st;
    4.   st.push(root);
    5.   while (!st.empty()) {
    6.       TreeNode *cur = st.top();  // 中
    7.       st.pop();
    8.       swap(cur->left, cur->right);
    9.       if (cur->right) st.push(cur->right);  // 右
    10.       if (cur->left) st.push(cur->left);  // 左
    11.   }
    12.   return root;
    13. }

  • 中序遍历 - 标记法

    1. TreeNode *invertTree(TreeNode *root) {
    2.   if (root == NULL) return NULL;
    3.   stack<TreeNode *> st;
    4.   st.push(root);
    5.   while (!st.empty()) {
    6.       TreeNode *cur = st.top();
    7.       st.pop();
    8.       if (cur != NULL) {
    9.           if (cur->right) st.push(cur->right);  // 右
    10.           st.push(cur);  // 中
    11.           st.push(NULL);
    12.           // 不在这翻转
    13.           if (cur->left) st.push(cur->left);  // 左
    14.       } else {
    15.           cur = st.top();
    16.           st.pop();
    17.           swap(cur->left, cur->right);  // 结点处理逻辑
    18.       }
    19.   }
    20.   return root;
    21. }

模拟广度优先遍历

  • 层序遍历
    TreeNode *invertTree(TreeNode *root) {
  if (root == NULL) return root;
  queue<TreeNode *> q;
  q.push(root);
  while (!q.empty()) {
      TreeNode *cur = q.front();
      q.pop();
      swap(cur->left, cur->right);
      if (cur->left) q.push(cur->left);
      if (cur->right) q.push(cur->right);
  }
  return root;
}