首页 > 代码库 > 翻转二叉树

翻转二叉树

2024-10-11 07:15:39   213人阅读

翻转一棵二叉树。 

样例：

  1            1
  / \          / \
2  3  => 3   2
   /           \
  4            4


问题比较简单，这里给出递归和非递归的做法。

递归实现：

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

//递归实现
void invertBinaryTree(TreeNode *root) {
    if (root == NULL) return;
    swap(node -> left, node -> right);
    invertBinaryTree(root->left);
    invertBinaryTree(root->right);
}

 

非递归实现：

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
    
//非递归实现    
void invertBinaryTree(TreeNode *root) {
    if (root == NULL) return;
    queue<TreeNode*> level;
    level.push(root);
    while (!level.empty()) {
         TreeNode* node = level.front();
         level.pop();
         swap(node->left, node->right);
         if (node->left != NULL) level.push(node->left);
         if (node->right != NULL) level.push(node->right);
     }
}

 

 

翻转二叉树


联系
我们