LeetCode226 翻转二叉树 LeetCode算法题解

原题目

翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ /\
1 3 6 9
输出：
4
/ \
7 2
/ \ /\
9 6 3 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
题目分析只要将每个节点的左右子树交换即可
前序，中序，后序，层序都可以
完整代码前序递归

struct TreeNode* invertTree(struct TreeNode* root){ if(root==NULL)return root; struct TreeNode *temp=root->right; root->right=root->left; root->left=temp; invertTree(root->left); invertTree(root->right); return root; }

前序迭代

struct TreeNode* invertTree(struct TreeNode* root){ if(root==NULL)return root; struct TreeNode* stack[200]; int top=0; stack[top++]=root; struct TreeNode *cur; while(top) { cur=stack[--top]; if(cur->right) stack[top++]=cur->right; if(cur->left) stack[top++]=cur->left; struct TreeNode *temp=cur->left; cur->left=cur->right; cur->right=temp; } return root; }

中序递归

struct TreeNode* invertTree(struct TreeNode* root){ if(root==NULL)return root; invertTree(root->left); struct TreeNode *temp=root->right; root->right=root->left; root->left=temp; invertTree(root->left); return root; }

【LeetCode226 翻转二叉树】层序迭代

struct TreeNode* invertTree(struct TreeNode* root){ if(root==NULL)return root; struct TreeNode* queue[200]; int front=0,rear=0; queue[rear++]=root; struct TreeNode *cur; while(front!=rear) { cur=queue[front++]; if(cur->left) queue[rear++]=cur->left; if(cur->right) q ueue[rear++]=cur->right; struct TreeNode *temp=cur->left; cur->left=cur->right; cur->right=temp; } return root; }