// 第 14 周 – 二叉树：遍历和递归操作
// 运行：go run ./w14/binarytree
package main

import (
	"fmt"
	"strings"
)

type Node struct {
	Value       rune
	Left, Right *Node
}

func leaf(v rune) *Node { return &Node{Value: v} }

func preorder(p *Node, out *[]string) {
	if p == nil {
		return
	}
	*out = append(*out, string(p.Value))
	preorder(p.Left, out)
	preorder(p.Right, out)
}

func inorder(p *Node, out *[]string) {
	if p == nil {
		return
	}
	inorder(p.Left, out)
	*out = append(*out, string(p.Value))
	inorder(p.Right, out)
}

func postorder(p *Node, out *[]string) {
	if p == nil {
		return
	}
	postorder(p.Left, out)
	postorder(p.Right, out)
	*out = append(*out, string(p.Value))
}

// levelOrder：用队列进行广度优先遍历
func levelOrder(root *Node) []string {
	var out []string
	q := []*Node{}
	if root != nil {
		q = append(q, root)
	}
	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		out = append(out, string(p.Value))
		if p.Left != nil {
			q = append(q, p.Left)
		}
		if p.Right != nil {
			q = append(q, p.Right)
		}
	}
	return out
}

func size(p *Node) int {
	if p == nil {
		return 0
	}
	return 1 + size(p.Left) + size(p.Right)
}

func leaves(p *Node) int {
	if p == nil {
		return 0
	}
	if p.Left == nil && p.Right == nil {
		return 1
	}
	return leaves(p.Left) + leaves(p.Right)
}

func height(p *Node) int {
	if p == nil {
		return -1
	}
	return 1 + max(height(p.Left), height(p.Right))
}

func contains(p *Node, x rune) bool {
	if p == nil {
		return false
	}
	return p.Value == x || contains(p.Left, x) || contains(p.Right, x)
}

func printSideways(p *Node, depth int) {
	if p == nil {
		return
	}
	printSideways(p.Right, depth+1)
	fmt.Println(strings.Repeat("      ", depth) + string(p.Value))
	printSideways(p.Left, depth+1)
}

func main() {
	root := &Node{'F',
		&Node{'B', leaf('A'), &Node{'D', leaf('C'), leaf('E')}},
		&Node{'G', nil, &Node{'I', leaf('H'), nil}}}

	var out []string
	preorder(root, &out)
	fmt.Println("preorder:   ", strings.Join(out, " "))
	out = nil
	inorder(root, &out)
	fmt.Println("inorder:    ", strings.Join(out, " "))
	out = nil
	postorder(root, &out)
	fmt.Println("postorder:  ", strings.Join(out, " "))
	fmt.Println("level order:", strings.Join(levelOrder(root), " "))
	fmt.Println("\ncount =", size(root), ", leaves =", leaves(root), ", height =", height(root))
	fmt.Println("contains('E') =", contains(root, 'E'), ", contains('Z') =", contains(root, 'Z'))
	fmt.Println("\nThe tree turned sideways:")
	printSideways(root, 0)
}