My Avatar

胡湘铭的博客

Coding and thinking!

Leetcode反转二叉树

2015年2月15日, 发表于 长春

如果你对本文有任何的建议或者疑问, 可以在 这里给我提 Issues, 谢谢! :)

反转二叉树

Invert a binary tree.

图片1

to: 图片

递归方法

这道题可以这样细化：反转二叉树的左右子树，然后将左右子树交换。所以用递归的思想是很自然的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//author:huxiangming
//email:husama@qq.com
/**
 * 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 =invertBinaryTree(root->right);
        root->right =invertBinaryTree(temp);
        return root;
    }
};

非递归方法：

用栈和队列都能模拟，思路差不多，就只放出用栈实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//author:huxiangming
//email:husama@qq.com
/**
 * 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;
        stack<TreeNode *> S;
        S.push(root);
        TreeNode *p;
        while (!S.empty()) {
            p=S.top();
            S.pop();
            TreeNode *pNode =p->left;
            p->left =p->right;
            p->right =pNode;
            if (p->left !=NULL)
                S.push(p->left);
            if (p->right !=NULL)
                S.push(p->right);
        }
        return root;
    }
};

很明显递归的算法要简洁易懂许多，但是效率不高，容易栈溢出，所以迭代和递归都要掌握。

Copyright © 2016 胡湘铭 - All rights reserved.