Invert Binary Tree

发布于 2025-02-22 13:01:29 字数 3357 浏览 0 评论 0 收藏 0

Source

leetcode: Invert Binary Tree | LeetCode OJ
lintcode: (175) Invert Binary Tree

Invert a binary tree.

Example
  1     1
 / \     / \
2   3  => 3   2
   /     \
  4     4
Challenge
Do it in recursion is acceptable, can you do it without recursion?

题解 1 - Recursive

二叉树的题用递归的思想求解自然是最容易的，此题要求为交换左右子节点，故递归交换之即可。具体实现可分返回值为空或者二叉树节点两种情况，返回值为节点的情况理解起来相对不那么直观一些。

C++ - return void

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *   int val;
 *   TreeNode *left, *right;
 *   TreeNode(int val) {
 *     this->val = val;
 *     this->left = this->right = NULL;
 *   }
 * };
 */
class Solution {
public:
  /**
   * @param root: a TreeNode, the root of the binary tree
   * @return: nothing
   */
  void invertBinaryTree(TreeNode *root) {
    if (root == NULL) return;

    TreeNode *temp = root->left;
    root->left = root->right;
    root->right = temp;

    invertBinaryTree(root->left);
    invertBinaryTree(root->right);
  }
};

C++ - return TreeNode *

/**
 * 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 == NULL) return NULL;

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

    return root;
  }
};

源码分析

分三块实现，首先是节点为空的情况，然后使用临时变量交换左右节点，最后递归调用，递归调用的正确性可通过画图理解。

复杂度分析

每个节点遍历一次，时间复杂度为 O(n)O(n)O(n), 使用了临时变量，空间复杂度为 O(1)O(1)O(1).

题解 2 - Iterative

递归的实现非常简单，那么非递归的如何实现呢？如果将递归改写成栈的实现，那么简单来讲就需要两个栈了，稍显复杂。其实仔细观察此题可发现使用 level-order 的遍历次序也可实现。即从根节点开始入队，交换左右节点，并将非空的左右子节点入队，从队列中取出节点，交换之，直至队列为空。

C++

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *   int val;
 *   TreeNode *left, *right;
 *   TreeNode(int val) {
 *     this->val = val;
 *     this->left = this->right = NULL;
 *   }
 * };
 */
class Solution {
public:
  /**
   * @param root: a TreeNode, the root of the binary tree
   * @return: nothing
   */
  void invertBinaryTree(TreeNode *root) {
    if (root == NULL) return;

    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
      // pop out the front node
      TreeNode *node = q.front();
      q.pop();
      // swap between left and right pointer
      swap(node->left, node->right);
      // push non-NULL node
      if (node->left != NULL) q.push(node->left);
      if (node->right != NULL) q.push(node->right);
    }
  }
};