leetcode 226. Invert Binary Tree（反转二叉树）

2017-02-22 · 1 min read

题意：反转一棵二叉树。。。字面意思理解即可。。就是把每一棵子树的左右孩子交换。。。

思路：直接照着题意做就好了。。。没有坑。。记录的原因是听说这题比较经典（虽然毫无难度...

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10class Solution {
11public:

 1        bool leaf(TreeNode* root)
 2        {
 3            if (root->left==NULL&&root->right==NULL) return true;
 4            return false;
 5        }
 6        void dfs(TreeNode* root)
 7        {
 8            if (leaf(root)) return;
 9            TreeNode* tmp = root->left;
10            root->left = root->right;
11            root->right = tmp;
12            if (root->left!=NULL) dfs(root->left);
13            if (root->right!=NULL) dfs(root->right);
14        }
15     TreeNode* invertTree(TreeNode* root) {
16        if (root==NULL) return NULL;
17        dfs(root);
18        return root;

    }
};