20210306学习记录

2021-03-06 学习记录

今天的学习内容：

1. 数据结构：树-二叉树
2. Leetcode刷题：#589 N叉树的前序遍历

1. 数据结构：树-二叉树

二叉树是日常算法中最常用的树，它有很多很优秀的性质。

1. 二叉树的第i层至多有2^(i-1)个节点
2. 深度为k的二叉树最多有(2^k)-1个节点
3. 若二叉树的叶子节点个数为m，度为2的节点树为n，则m=n+1
4. 具有n个节点的完全二叉树的深度为[log(2,n)]-1，其中[n]表示不超过n的最大整数，log(m,n)表示以m为底n的对数

二叉树这里不需要考虑并发的问题，单棵树的创建不存在多个线程同时创建的问题，二叉树的遍历不存在对节点值的修改，也不存在并发同步问题。

package main

import (
	"fmt"
	"reflect"
)

//BinaryTree the binary tree structure
type BinaryTree struct {
	val   interface{}
	left  *BinaryTree
	right *BinaryTree
}

// CreateAnyTypeSlice converse interface{} to slice
func CreateAnyTypeSlice(slice interface{}) ([]interface{}, bool) {
	val, ok := isSlice(slice)
	if !ok {
		return nil, false
	}

	sliceLen := val.Len()

	out := make([]interface{}, sliceLen)

	for i := 0; i < sliceLen; i++ {
		out[i] = val.Index(i).Interface()
	}

	return out, true
}

func isSlice(slice interface{}) (val reflect.Value, ok bool) {
	val = reflect.ValueOf(slice)

	if val.Kind() == reflect.Slice {
		ok = true
	}

	return
}

// CreateByPreOrderSequence create a binary tree by a preorder sequence(which contains node and nil, nil means an empty subtree)
func CreateByPreOrderSequence(arr interface{}) *BinaryTree {
	slice, ok := CreateAnyTypeSlice(arr)
	if !ok {
		fmt.Errorf("not a slice")
		return nil
	}
	if len(slice) == 0 {
		return new(BinaryTree)
	}

	var create func([]interface{}, *int) *BinaryTree
	create = func(slice []interface{}, flag *int) *BinaryTree {
		if *flag < len(slice)-1 {
			*flag = *flag + 1
		}
		if slice[*flag] == nil {
			return nil
		}
		node := new(BinaryTree)
		node.val = slice[*flag]
		node.left = create(slice, flag)
		node.right = create(slice, flag)

		return node
	}

	flag := -1
	binaryTree := create(slice, &flag)

	// fmt.Println(binaryTree.TraversePreOrder())
	return binaryTree
}

// TraversePreOrder traverse in preorder sequence
func (binaryTree *BinaryTree) TraversePreOrder() interface{} {

	var traverse func(root *BinaryTree)
	var res []interface{}
	traverse = func(root *BinaryTree) {
		if root == nil {
			return
		}
		res = append(res, root.val)
		traverse(root.left)
		traverse(root.right)
	}

	traverse(binaryTree)
	return res
}

// TraverseInOrder traverse in inorder sequence
func (binaryTree *BinaryTree) TraverseInOrder() interface{} {
	var traverse func(root *BinaryTree)
	var res []interface{}
	traverse = func(root *BinaryTree) {
		if root == nil {
			return
		}

		traverse(root.left)
		res = append(res, root.val)
		traverse(root.right)
	}

	traverse(binaryTree)
	return res
}

// TraversePostOrder traverse in postorder sequence
func (binaryTree *BinaryTree) TraversePostOrder() interface{} {

	var traverse func(root *BinaryTree)
	var res []interface{}
	traverse = func(root *BinaryTree) {
		if root == nil {
			return
		}
		traverse(root.left)
		traverse(root.right)
		res = append(res, root.val)
	}

	traverse(binaryTree)
	return res
}

出现的问题主要有：

1. 创建树的函数中，匿名函数的写法一开始存在一些问题，一开始我的写法如下：

func CreateByPreOrderSequence(arr interface{}) *BinaryTree {
	slice, ok := CreateAnyTypeSlice(arr)
	
    // ... 边界检查

	// var create func([]interface{}, *int) *BinaryTree
    create := func(slice []interface{}, flag *int) *BinaryTree {
		if *flag < len(slice)-1 {
			*flag = *flag + 1
		}
		if slice[*flag] == nil {
			return nil
		}
		node := new(BinaryTree)
		node.val = slice[*flag]
		node.left = create(slice, flag)
		node.right = create(slice, flag)

		return node
	}

	// ...
}

但是这样的话内部的traverse()函数将被认为是未定义的，这里必须先声明函数，然后再重新赋值函数实现：

func CreateByPreOrderSequence(arr interface{}) *BinaryTree {
	slice, ok := CreateAnyTypeSlice(arr)
	// ... 边界检查

	var create func([]interface{}, *int) *BinaryTree
	create = func(slice []interface{}, flag *int) *BinaryTree {
		if *flag < len(slice)-1 {
			*flag = *flag + 1
		}
		if slice[*flag] == nil {
			return nil
		}
		node := new(BinaryTree)
		node.val = slice[*flag]
		node.left = create(slice, flag)
		node.right = create(slice, flag)

		return node
	}

	flag := -1
	binaryTree := create(slice, &flag)

	return binaryTree
}

且这里由于数组在每次遍历每次递归调用都要加一，所以这里需要传入指针实现修改。

这里还存在一个未解决的问题：如果我们不是采取这种函数的结构，而是将这个函数声明为BinaryTree结构的一个方法，即func (binaryTree *BinaryTree) CreateByPreOrderSequence(arr interface{}) error，其他部分不变，最后返回nil，那么最终binaryTree的值在这个函数内被成功修改，但是main函数中的binaryTree依然是nil。

func (binaryTree *BinaryTree) CreateByPreOrderSequence(arr interface{}) error {
	// ... 同上

	var create func([]interface{}, *int) *BinaryTree
	create = func(slice []interface{}, flag *int) *BinaryTree {
		// ... 同上
	}

	flag := -1
	binaryTree := create(slice, &flag)

	return nil
}

初步猜测是binaryTree的值是create函数返回地址处的值，但是main函数中的binaryTree依然指向这个变量new的时候分配的内存空间的地址，这俩地址并不相同，导致main函数中无法读取binaryTree的值，结果返回nil。

2. Leetcode刷题

#589 N叉树的前序遍历

这个题比较简单，遍历n叉树，这里可以使用递归法和非递归法，先是递归法的代码：

func preorder(root *Node) []int {
    var res []int
    if root == nil {
        return res
    }
    
    var traverse func(*Node) 
    traverse = func(root *Node) {
        if root == nil {
            return
        }
        res = append(res, root.Val)
        for _, child := range root.Children {
            traverse(child)
        }
    }

    traverse(root)
    return res
}

然后是非递归法，参考二叉树前序遍历的非递归法，我们维护一个栈，每次遍历根节点后将其出栈，随后其所有子节点入栈。这里需要前序遍历，我们需要将每个根节点的所有子节点逆序入栈，这样才能保证每次即将遍历的下一个节点刚好在栈顶的位置。

func preorder(root *Node) []int {
    var res []int
    var stack []*Node
    if root == nil {
        return res
    }
    stack = append(stack, root)

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        
        for i := len(node.Children)-1; i >= 0; i-- {
            stack = append(stack, node.Children[i])
        }
    }

    return res
}