前言

題目比較好理解，就是翻轉(zhuǎn)二叉樹

代碼

c語言實現(xiàn)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>#define N 105struct TreeNode
{int val;TreeNode* left;TreeNode* right;
};TreeNode *queue[N];
TreeNode *stack[N];//創(chuàng)建樹
void create_tree(TreeNode *&root)
{char c;scanf("%c", &c);if (c == '0'){root = NULL;}else{root = (TreeNode*)malloc(sizeof(TreeNode));root->val = c;create_tree(root->left);create_tree(root->right);}
}//打印樹
void print_tree(TreeNode *root)
{if (root != NULL){printf("%c", root->val);print_tree(root->left);print_tree(root->right);}
}//采用遞歸
void reverse_tree(TreeNode *root)
{if (root != NULL){TreeNode *s;s = root->left;root->left = root->right;root->right = s;reverse_tree(root->left);reverse_tree(root->right);}
}//采用隊列
void reverse_tree_queue(TreeNode *root)
{TreeNode *temp, *p = root;int front, rear;if (root != NULL){queue[0] = root;front = -1;rear = 0;while (front < rear){p = queue[++front];temp = p->left;p->left = p->right;p->right = temp;if (p->left != NULL){queue[++rear] = p->left;}if (p->right != NULL){queue[++rear] = p->right;}}}
}//采用棧
void reverse_tree_stack(TreeNode *root)
{int top = -1;TreeNode *p, *bt = root;if (root != NULL){stack[++top] = root;while (top != -1){bt = stack[top--];p = bt->right;bt->right = bt->left;bt->left = p;if (bt->left){stack[++top] = bt->left;}if (bt->right){stack[++top] = bt->right;}}}}int main(int argc, char* agrv[])
{TreeNode *bt;create_tree(bt);print_tree(bt);printf("\n");reverse_tree(bt);print_tree(bt);printf("\n");reverse_tree_queue(bt);print_tree(bt);printf("\n");reverse_tree_stack(bt);print_tree(bt);printf("\n");return 0;
}

測試代碼

abc000de00f00res:
abcdef
adfebc
abcdef
adfebc

python 實現(xiàn)

#!/bin/pythonimport sys, osclass TreeNode:def __init__(self, x):self.val = x;self.left = None;self.right = None;def list_to_node(values):if not values:return Noneroot = TreeNode(int(values[0]))node_queue = [root]front = 0index = 1while index < len(values):node = node_queue[front]front += 1item = values[index]index += 1if item != 'null':left_num = int(item)node.left = TreeNode(left_num)node_queue.append(node.left)if index >= len(values):breakitem = values[index]index += 1if item != 'null':right_num = int(item)node.right = TreeNode(right_num)node_queue.append(node.right)return rootclass Solution:def preorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""ret = []stack = [root]while stack:node = stack.pop()if node:ret.append(node.val)stack.append(node.right)stack.append(node.left)return retdef reverse_tree(root):if root is not None:root.left, root.right = root.right, root.leftreverse_tree(root.left)reverse_tree(root.right)return rootdef main():str_node = list(map(str, sys.stdin.readline().strip().split()))root = list_to_node(str_node)pret = Solution().preorderTraversal(root)print(pret)root = reverse_tree(root)pret = Solution().preorderTraversal(root)print(pret)if __name__ == '__main__':main()

測試代碼

3 9 20 null null 15 73/ \9  20/  \15   7res:
[3, 9, 20, 15, 7]
[3, 20, 7, 15, 9]

總結(jié)

以上是生活随笔為你收集整理的翻转二叉树 c语言实现 递归 栈 队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。