golang 二叉树后序遍历

后序遍历

左右中，这个顺序可以自底向上的获取二叉树的所有子树，这是它的特性，当你遇到的场景需要将二叉树的每个节点当作根结点做统计，不妨试试后序遍历。

leetcode145 二叉树的后序遍历

code递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    ret := []int{}
    dfs(root, &ret)
    return ret
}

func dfs(root *TreeNode, ret *[]int) {
    if root != nil {
        dfs(root.Left, ret)
        dfs(root.Right, ret)
        *ret = append(*ret, root.Val)
    }
}

code非递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    res := []int{}
    stack := []*TreeNode{}
    cur := root

    for len(stack) > 0 || cur != nil {
        if cur != nil {
            res = append(res, cur.Val)
            stack = append(stack, cur)
            cur = cur.Right
        } else {
            cur = stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            cur = cur.Left
        }
    }

    reverse(res)

    return res
}

func reverse(res []int) {
	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}
}

leetcode563 二叉树的坡度

code

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findTilt(root *TreeNode) int {
    ret := 0
    dfs(root, &ret)
    return ret
}

func dfs(root *TreeNode, ret *int) int {
    if root == nil {
        return 0
    }
    left, right := dfs(root.Left, ret), dfs(root.Right, ret)
    *ret += abs(left-right)
    return left+right+root.Val
}

func abs(a int) int {
    if a < 0 {
        return -1 * a
    }
    return a
}

leetcode572 另一棵树的子树

code

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil {
        return false
    }
    if isSameTree(root, subRoot) {
        return true
    }
    left, right := isSubtree(root.Left, subRoot), isSubtree(root.Right, subRoot)
    return left || right
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    } else if p != nil && q != nil {
        if p.Val != q.Val {
            return false
        } else {
            return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
        }
    } else {
        return false
    }
}

leetcode652 寻找重复的子树

code

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {

    count := map[string]int{}
    ret := []*TreeNode{}

    dfs(root, &ret, count)
    return ret

}

func dfs(node *TreeNode, ret *[]*TreeNode, count map[string]int) string {
    if node != nil {
        left, right := dfs(node.Left, ret, count), dfs(node.Right, ret, count)
        key := strconv.Itoa(node.Val)+ "," + left + "," + right
        count[key]++
        if count[key] == 2 {
            *ret = append(*ret, node)
        }
        return key
    } else {
        return ""
    }
}

leetcode1339 分裂二叉树的最大乘积

code

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxProduct(root *TreeNode) int {
    sum := sum(root)
    max := 0
    
    dfs(root, sum, &max)
   
    mod := int(math.Pow(10,9)+7)
    return max % mod
}

func sum(root *TreeNode) int {
    if root == nil {
        return 0
    }

    return root.Val + sum(root.Left) + sum(root.Right)
}

func dfs(root *TreeNode, sum int, max *int) int {
    if root == nil {
        return 0
    }
    left, right := dfs(root.Left, sum, max), dfs(root.Right, sum, max)
    total := root.Val + left + right

    *max = maxfunc(*max, (sum-total) * total)

    return total
}

func maxfunc(a, b int) int {
    if a < b {
        return b
    }
    return a
}