#
##
###
********
********
********
-
-
####
```go
func preorderTraversal(root *TreeNode) {
if root==nil{
return
}
//
fmt.Println(root.Val)
preorderTraversal(root.Left)
preorderTraversal(root.Right)
}
```
####
```go
// V3
func preorderTraversal(root *TreeNode) []int {
//
if root == nil{
return nil
}
result:=make([]int,0)
stack:=make([]*TreeNode,0)
for root!=nil || len(stack)!=0{
for root !=nil{
//
result=append(result,root.Val)
stack=append(stack,root)
root=root.Left
}
// pop
node:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
root=node.Right
}
return result
}
```
####
```go
// stack
func inorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
if root == nil {
return result
}
stack := make([]*TreeNode, 0)
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left //
}
//
val := stack[len(stack)-1]
stack = stack[:len(stack)-1]
result = append(result, val.Val)
root = val.Right
}
return result
}
```
####
```go
func postorderTraversal(root *TreeNode) []int {
// lastVisit
if root == nil {
return nil
}
result := make([]int, 0)
stack := make([]*TreeNode, 0)
var lastVisit *TreeNode
for root != nil || len(stack) != 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
//
node:= stack[len(stack)-1]
//
if node.Right == nil || node.Right == lastVisit {
stack = stack[:len(stack)-1] // pop
result = append(result, node.Val)
//
lastVisit = node
} else {
root = node.Right
}
}
return result
}
```
-
#### DFS -
```go
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func preorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
dfs(root, &result)
return result
}
// V1
func dfs(root *TreeNode, result *[]int) {
if root == nil {
return
}
*result = append(*result, root.Val)
dfs(root.Left, result)
dfs(root.Right, result)
}
```
#### DFS -
```go
// V2
func preorderTraversal(root *TreeNode) []int {
result := divideAndConquer(root)
return result
}
func divideAndConquer(root *TreeNode) []int {
result := make([]int, 0)
// (null & leaf)
if root == nil {
return result
}
// (Divide)
left := divideAndConquer(root.Left)
right := divideAndConquer(root.Right)
// (Conquer)
result = append(result, root.Val)
result = append(result, left...)
result = append(result, right...)
return result
}
```
> DFS
#### BFS
```go
func levelOrder(root *TreeNode) [][]int {
//
result := make([][]int, 0)
if root == nil {
return result
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
list := make([]int, 0)
// length
//
l := len(queue)
for i := 0; i < l; i++ {
//
level := queue[0]
queue = queue[1:]
list = append(list, level.Val)
if level.Left != nil {
queue = append(queue, level.Left)
}
if level.Right != nil {
queue = append(queue, level.Right)
}
}
result = append(result, list)
}
return result
}
```
###
-
-
-
-
-
-
```go
func traversal(root *TreeNode) ResultType {
// nil or leaf
if root == nil {
// do something and return
}
// Divide
ResultType left = traversal(root.Left)
ResultType right = traversal(root.Right)
// Conquer
ResultType result = Merge from left and right
return result
}
```
####
```go
// V2
func preorderTraversal(root *TreeNode) []int {
result := divideAndConquer(root)
return result
}
func divideAndConquer(root *TreeNode) []int {
result := make([]int, 0)
// (null & leaf)
if root == nil {
return result
}
// (Divide)
left := divideAndConquer(root.Left)
right := divideAndConquer(root.Right)
// (Conquer)
result = append(result, root.Val)
result = append(result, left...)
result = append(result, right...)
return result
}
```
####
```go
func MergeSort(nums []int) []int {
return mergeSort(nums)
}
func mergeSort(nums []int) []int {
if len(nums) right[r] {
result = append(result, right[r])
r++
} else {
result = append(result, left[l])
l++
}
}
//
result = append(result, left[l:]...)
result = append(result, right[r:]...)
return
}
```
>
####
```go
func QuickSort(nums []int) []int {
//
quickSort(nums, 0, len(nums)-1)
return nums
}
//
func quickSort(nums []int, start, end int) {
if start < end {
// divide
pivot := partition(nums, start, end)
quickSort(nums, 0, pivot-1)
quickSort(nums, pivot+1, end)
}
}
//
func partition(nums []int, start, end int) int {
p := nums[end]
i := start
for j := start; j < end; j++ {
if nums[j] < p {
swap(nums, i, j)
i++
}
}
//
swap(nums, i, end)
return i
}
func swap(nums []int, i, j int) {
t := nums[i]
nums[i] = nums[j]
nums[j] = t
}
```
>
> 0length-1
#### maximum-depth-of-binary-tree
[maximum-depth-of-binary-tree](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
>
```go
func maxDepth(root *TreeNode) int {
//
if root == nil {
return 0
}
// divide
left := maxDepth(root.Left)
right := maxDepth(root.Right)
// conquer
if left > right {
return left + 1
}
return right + 1
}
```
#### balanced-binary-tree
[balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)
>
&& && 0
```go
func isBalanced(root *TreeNode) bool {
if maxDepth(root) == -1 {
return false
}
return true
}
func maxDepth(root *TreeNode) int {
// check
if root == nil {
return 0
}
left := maxDepth(root.Left)
right := maxDepth(root.Right)
// -1
if left == -1 || right == -1 || left-right > 1 || right-left > 1 {
return -1
}
if left > right {
return left + 1
}
return right + 1
}
```
>
#### binary-tree-maximum-path-sum
[binary-tree-maximum-path-sum](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)
> ****
```go
type ResultType struct {
SinglePath int //
MaxPath int // +
}
func maxPathSum(root *TreeNode) int {
result := helper(root)
return result.MaxPath
}
func helper(root *TreeNode) ResultType {
// check
if root == nil {
return ResultType{
SinglePath: 0,
MaxPath: -(1 right.SinglePath {
result.SinglePath = max(left.SinglePath + root.Val, 0)
} else {
result.SinglePath = max(right.SinglePath + root.Val, 0)
}
//
maxPath := max(right.MaxPath, left.MaxPath)
result.MaxPath = max(maxPath,left.SinglePath+right.SinglePath+root.Val)
return result
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
```
#### lowest-common-ancestor-of-a-binary-tree
[lowest-common-ancestor-of-a-binary-tree](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
> ,
```go
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// check
if root == nil {
return root
}
// root
if root == p || root == q {
return root
}
// Divide
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
// Conquer
//
if left != nil && right != nil {
return root
}
if left != nil {
return left
}
if right != nil {
return right
}
return nil
}
```
### BFS
#### binary-tree-level-order-traversal
[binary-tree-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
> ****
O(logN)
```go
func levelOrder(root *TreeNode) [][]int {
result := make([][]int, 0)
if root == nil {
return result
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
list := make([]int, 0)
// length
//
l := len(queue)
for i := 0; i < l; i++ {
//
level := queue[0]
queue = queue[1:]
list = append(list, level.Val)
if level.Left != nil {
queue = append(queue, level.Left)
}
if level.Right != nil {
queue = append(queue, level.Right)
}
}
result = append(result, list)
}
return result
}
```
#### binary-tree-level-order-traversal-ii
[binary-tree-level-order-traversal-ii](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)
>
```go
func levelOrderBottom(root *TreeNode) [][]int {
result := levelOrder(root)
//
reverse(result)
return result
}
func reverse(nums [][]int) {
for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
nums[i], nums[j] = nums[j], nums[i]
}
}
func levelOrder(root *TreeNode) [][]int {
result := make([][]int, 0)
if root == nil {
return result
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
list := make([]int, 0)
// length
//
l := len(queue)
for i := 0; i < l; i++ {
//
level := queue[0]
queue = queue[1:]
list = append(list, level.Val)
if level.Left != nil {
queue = append(queue, level.Left)
}
if level.Right != nil {
queue = append(queue, level.Right)
}
}
result = append(result, list)
}
return result
}
```
#### binary-tree-zigzag-level-order-traversal
[binary-tree-zigzag-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)
> Z
```go
func zigzagLevelOrder(root *TreeNode) [][]int {
result := make([][]int, 0)
if root == nil {
return result
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
toggle := false
for len(queue) > 0 {
list := make([]int, 0)
//
l := len(queue)
for i := 0; i < l; i++ {
//
level := queue[0]
queue = queue[1:]
list = append(list, level.Val)
if level.Left != nil {
queue = append(queue, level.Left)
}
if level.Right != nil {
queue = append(queue, level.Right)
}
}
if toggle {
reverse(list)
}
result = append(result, list)
toggle = !toggle
}
return result
}
func reverse(nums []int) {
for i := 0; i < len(nums)/2; i++ {
t := nums[i]
nums[i] = nums[len(nums)-1-i]
nums[len(nums)-1-i] = t
}
}
```
###
#### validate-binary-search-tree
[validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)
>
1
2 MAX < < MIN
```go
// v1
func isValidBST(root *TreeNode) bool {
result := make([]int, 0)
inOrder(root, &result)
// check order
for i := 0; i < len(result) - 1; i++{
if result[i] >= result[i+1] {
return false
}
}
return true
}
func inOrder(root *TreeNode, result *[]int) {
if root == nil{
return
}
inOrder(root.Left, result)
*result = append(*result, root.Val)
inOrder(root.Right, result)
}
```
```go
// v2
type ResultType struct {
IsValid bool
//
Max *TreeNode
Min *TreeNode
}
func isValidBST2(root *TreeNode) bool {
result := helper(root)
return result.IsValid
}
func helper(root *TreeNode) ResultType {
result := ResultType{}
// check
if root == nil {
result.IsValid = true
return result
}
left := helper(root.Left)
right := helper(root.Right)
if !left.IsValid || !right.IsValid {
result.IsValid = false
return result
}
if left.Max != nil && left.Max.Val >= root.Val {
result.IsValid = false
return result
}
if right.Min != nil && right.Min.Val BST
```go
// DFS
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
root = &TreeNode{Val: val}
return root
}
if root.Val > val {
root.Left = insertIntoBST(root.Left, val)
} else {
root.Right = insertIntoBST(root.Right, val)
}
return root
}
```
##
-
- DFS
- BFS
##
- [ ] [maximum-depth-of-binary-tree](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
- [ ] [balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)
- [ ] [binary-tree-maximum-path-sum](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)
- [ ] [lowest-common-ancestor-of-a-binary-tree](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
- [ ] [binary-tree-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
- [ ] [binary-tree-level-order-traversal-ii](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)
- [ ] [binary-tree-zigzag-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)
- [ ] [validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)
- [ ] [insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)