本文共 955 字，大约阅读时间需要 3 分钟。

翻转一棵二叉树

样例

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

递归版本

先翻转左子树，后翻转右子树，然后对整个树进行翻转

void swapTree(TreeNode *&root){    TreeNode *tmp = root->left;    root->left = root->right;    root->right = tmp;}void invertBinaryTree(TreeNode *root) {    // write your code here    if(root == NULL)        return;    invertBinaryTree(root->left);    invertBinaryTree(root->right);    swapTree(root);}

非递归版本

非递归版本用栈来实现，到访问到头节点的时候，将其左子树和右子树互换即可。

void swapTree(TreeNode *&root){    TreeNode *tmp = root->left;    root->left = root->right;    root->right = tmp;}void invertBinaryTree(TreeNode *root) {    // write your code here    if(root == NULL)        return;    stack
   
     stk;    stk.push(root);    while(!stk.empty())    {        TreeNode *tmp = stk.top();        stk.pop();        swapTree(tmp);        if(tmp->left)            stk.push(tmp->left);        if(tmp->right)            stk.push(tmp->right);    }}
   

(175) Invert Binary Tree 
）

转载地址：http://wagsi.baihongyu.com/