ツリーc言語を反転して再帰スタックキューを実現

前言
問題は分かりやすいですが、二叉木をひっくり返すことです.
コード#コード#
c言語実装

#include
#include
#include

#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("
");
        reverse_tree(bt);
        print_tree(bt);
        printf("
");
        reverse_tree_queue(bt);
        print_tree(bt);
        printf("
");
        reverse_tree_stack(bt);
        print_tree(bt);
        printf("
");

        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]