leetcode-二叉树

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type stack struct {
	BinTree []*TreeNode
	Top     int
}

func (nodeStack *stack) push(node *TreeNode) {
	nodeStack.BinTree = append(nodeStack.BinTree, node)
	nodeStack.Top++
}

func (nodeStack *stack) pop() *TreeNode {
	var res *TreeNode
	nodeStack.Top--
	if nodeStack.Top < 0 {
		res = nil
	} else {
		res = nodeStack.BinTree[nodeStack.Top]
	}
	nodeStack.BinTree = nodeStack.BinTree[:nodeStack.Top]
	return res
}

func inorderTraversal1(root *TreeNode) []int {
	res := []int{}
	myStack := &stack{[]*TreeNode{}, 0}
	for nil != root || myStack.Top != 0 {
		for nil != root {
			myStack.push(root)
			root = root.Left
		}
		root = myStack.pop()
		res = append(res, root.Val)
		root = root.Right
	}
	return res
}

func inorderTraversal(root *TreeNode) []int {
	res := []int{}
	myStack := &stack{[]*TreeNode{}, 0}
	for nil != root || myStack.Top != 0 {
		for nil != root {
			myStack.push(root)
			root = root.Left
		}
		root = myStack.pop()
		res = append(res, root.Val)
		root = root.Right
	}
	return res
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
	lens = len(inorder)
	mid := 0
	for i := 0; i < lens; i++ {
		if inorder[i] == postorder[lens-1] {
			mid = i
		}
	}
	return &TreeNode{inorder[mid].Val, buildTree(inorder[:mid], postorder[:mid]), buildTree(inorder[mid+1:lens], postorder[mid:lens-1])}
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
	if nil == root {
		return true
	}
	return isSym(root.Left, root.Right)
}

func isSym(left, right *TreeNode) bool {
	if nil == left && nil == right {
		return true
	}
	if nil == left || nil == right || left.Val != right.Val {
		return false
	}
	outerRes := isSym(left.Left, right.Right)
	innerRes := isSym(left.right, right.Left)
	return outerRes && innerRes
}

func isSymmetric1(root *TreeNode) bool {
	s := *stack{0, nil, nil}
	if root == nil {
		return true
	}
	stack.push(root.Left)
	stack.push(root.Right)
	for s.Top > 0 {
		left := s.pop()
		right := s.pop()
		if left == nil && right == nil {
			continue
		}
		if left == nil || right == nil || left.Val == right.Val {
			return false
		}
		s.push(left.Left)
		s.push(right.Right)
		s.push(left.Right)
		s.push(right.Left)
	}
	return true
}

func maxDepth(root *TreeNode) int {
	if nil == root {
		return 0
	}
	leftD := maxDepth(root.Left)
	rightD := maxDepth(root.Right)
	if leftD > rightD {
		return leftD + 1
	} else {
		return rightD + 1
	}
}

func maxDepth1(root *TreeNode) int {
	deps := 0
	que := []*TreeNode{root}
	lens := len(que)
	for lens > 0 {
		for i := 0; i < lens; i++ {
			if nil == que[i] {
				continue
			}
			que = append(que, que[i].Left)
			que = append(que, que[i].Right)
		}
		que = que[lens:]
		lens = lens(que)
		if lens > 0 {
			deps++
		}
	}
	return deps
}

func levelOrderBottom(root *TreeNode) [][]int {
	res := [][]int{}
	if nil == root {
		return res
	}
	que := []*TreeNode{root}
	lens := len(que)
	for lens > 0 {
		level := []int{}
		for i := 0; i < lens; i++ {
			level = append(level, que[i].Val)
			if nil != que[i].Left {
				que = append(que, que[i].Left)
			}
			if nil != que[i].Right {
				que = append(que, que[i].Right)
			}
		}
		que = que[lens:]
		lens = len(que)
		res = append([][]int{level}, res)
	}
	return res
}

func levelOrderBottom1(root *TreeNode) [][]int {
	res := [][]int{}
	res = levelOrder(0, root, res)
}

func levelOrder(level int, root *TreeNode, res [][]int) [][]int {
	if nil == root {
		return res
	}
	if _, exist := res[level]; !exist {
		res = append(res, []int)
	}
	res[level] = append(res[level], root.Val)
	res = levelOrder(level+1, root.Left, res)
	return levelOrder(level+1, root.Right, res)
}

func minDepth(root *TreeNode) int {
	if nil == root {
		return 0
	}
	left := minDepth(root.Left)
	right := minDepth(root.Right)
	if left == 0 {
		return right + 1
	} else if right == 0 {
		return left + 1
	} else {
		if left > right {
			return right + 1
		} else {
			return left + 1
		}
	}
}

func isBalanced(root *TreeNode) bool {
	res := false
	dep := isBlan(root)
	if dep > 0 {
		res = true
	}
	return res
}

func isBlan(root *TreeNode) int {
	if nil == root {
		return 0
	}
	left := isBlan(root.Left)
	right := isBlan(root.Right)
	if left < 0 || right < 0 {
		return -1
	}
	diff := left - right
	if diff < -1 || diff > 1 {
		return -1
	} else if diff >= 0 {
		return left + 1
	} else {
		return right + 1
	}
}

func zigzagLevelOrder(root *TreeNode) [][]int {
	res := [][]int{}
	return recursive(0, root, res)
}

func recursive(dep int, root *TreeNode, res [][]int) [][]int {
	if nil == root {
		return res
	}
	if dep+1 > lens(res) {
		res = append(res, []int)
	}
	if dep/2 == 0 {
		res[dep] = append(res[dep], root.Val)
	} else {
		res[dep] = append([]int{root.Val}, res[dep]...)
	}
	res := recursive(dep+1, root.Left, res)
	return recursive(dep+1, root.Right, res)
}

func zigzagLevelOrder1(root *TreeNode) [][]int {
	res := [][]int{}
	que := []*TreeNode{root}
	lens := len(que)
	dep := 0
	for lens > 0 {
		level := []int{}
		for i := 0; i < lens; i++ {
			if nil == que[i] {
				continue
			}
			if dep%2 == 0 {
				level = append(level, que[i].Val)
			} else {
				level = append([]int{que[i].Val}, level...)
			}
			que = append(que, que[i].Left)
			que = append(que, que[i].Right)
		}
		res = append(res, level)
		que = que[lens:]
		lens = len(que)
		dep++
	}
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	head := preorder[0]
	index := 0
	for i := 0; i < len(inorder); i++ {
		if inorder[i] == head {
			index = i
		}
	}
	return &TreeNode{root.Val, buildTree(preorder[1:index+1], inorder[:index]), buildTree(preorder[index+1:], inorder[index+1:])}
}

func hasPathSum(root *TreeNode, sum int) bool {
	if root == nil {
		return false
	}
	if root.Left == nil && root.Right == nil {
		return root.Val == sum
	}
	sum -= sum - root.Val
	if root.Left != nil {
		leftRes := hasPathSum(root.Left, sum)
	}
	if root.Left != nil {
		rightRes := hasPathSum(root.Right, sum)
	}
	return leftRes && rightRes
}

func insertionSortList(head *ListNode) *ListNode {
	myHead := &ListNode{0, nil}
	for head != nil {
		node := head
		for nowHead := myHead; nowHead.Next != nil; nowHead = nowHead.Next {
			if nowHead.Next.Val > node.Val {
				node.Next = nowHead.Next
				nowHead.Next = node
				break
			}
		}
	}
	return myHead
}

func rightSideView(root *TreeNode) []int {
	que := []*TreeNode{root}
	lens := 1
	res := []int{}
	for lens > 0 {
		level := []int{}
		for i := 0; i < lens; i++ {
			if que[i] == nil {
				continue
			}
			level = append(level, que[i].Val)
			que = append(que, que[i].Left)
			que = append(que, que[i].Right)
		}
		res = append(res, level[lens-1])
		que = que[:lens]
		lens = len(que)
	}
	return res
}

func rangeSumBST(root *TreeNode, L int, R int) int {
	sum := 0
	if nil == root {
		return 0
	}
	if root.Val >= L {
		sum += rangeSumBST(root.Left, L, R)
	}
}