翻转二叉树 c语言实现递归栈队列

素颜马尾好姑娘i 2022-05-14 06:47 206阅读 0赞

# 前言 #

题目比较好理解，就是翻转二叉树

# 代码 #

## c语言实现 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define N 105
    
    
    struct TreeNode
    {
            int val;
            TreeNode* left;
            TreeNode* right;
    };
    
    TreeNode *queue[N];
    TreeNode *stack[N];
    
    
    //创建树
    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;
    }

## 测试代码 ##

abc000de00f00
    
    
    res:
    abcdef
    adfebc
    abcdef
    adfebc

## python 实现 ##

#!/bin/python
    
    import sys, os
    
    class TreeNode:
        def __init__(self, x):
            self.val = x;
            self.left = None;
            self.right = None;
    
    
    def list_to_node(values):
        if not values:
            return None
        root = TreeNode(int(values[0]))
        node_queue = [root]
        front = 0
        index = 1
        while index < len(values):
            node = node_queue[front]
            front += 1
    
            item = values[index]
            index += 1
    
            if item != 'null':
                left_num = int(item)
                node.left = TreeNode(left_num)
                node_queue.append(node.left)
    
            if index >= len(values):
                break
    
            item = values[index]
            index += 1
            if item != 'null':
                right_num = int(item)
                node.right = TreeNode(right_num)
                node_queue.append(node.right)
        return root
    
    class 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 ret
    
    def reverse_tree(root):
        if root is not None:
            root.left, root.right = root.right, root.left
            reverse_tree(root.left)
            reverse_tree(root.right)
        return root
    
    
    def 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 7
    
        3
       / \
      9  20
        /  \
       15   7
    
    res:
    [3, 9, 20, 15, 7]
    [3, 20, 7, 15, 9]