2019-08-04
2019-08-04 本文已影响0人
Jiawei_84a5
Validate Binary Search Tree
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func isValidBST(root *TreeNode) bool {
return rec(root, nil, nil)
}
func rec(node *TreeNode, min, max *int) bool {
if node == nil {
return true
}
if min != nil && node.Val <= *min || max != nil && node.Val >= *max {
return false
}
return rec(node.Left, min, &node.Val) && rec(node.Right, &node.Val, max)
}
Increasing Order Search Tree
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
var ret = TreeNode{Val: 0}
var tmp = &ret
func increasingBST(root *TreeNode) *TreeNode {
if root == nil {
return root
}
increasingBST(root.Left)
tmp.Right = &TreeNode{
Val: root.Val,
}
tmp = tmp.Right
increasingBST(root.Right)
return ret.Right
}
Print Binary Tree
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/**
先得到树的最大高度h
打印的宽度等于2的h次方-1
*/
var ret [][]string
func printTree(root *TreeNode) [][]string {
if root == nil {
return nil
}
h := getHeight(root)
w := pow(2, h) - 1
ret = make([][]string, h)
for k := range ret {
s := make([]string, w)
for key := range s {
s[key] = ""
}
ret[k] = s
}
helper(root, 0, 0, w)
return ret
}
func helper(root *TreeNode, level, l, r int) {
if root != nil {
mid := l + (r-l)/2
ret[level][mid] = strconv.Itoa(root.Val)
helper(root.Left, level+1, l, mid-1)
helper(root.Right, level+1, mid+1, r)
}
}
func getHeight(root *TreeNode) int {
if root == nil {
return 0
}
l := getHeight(root.Left)
r := getHeight(root.Right)
if l > r {
return l + 1
}
return r + 1
}
func pow(x, y int) int {
ret := x
for i := 1; i < y; i++ {
ret *= x
}
return ret
}