LeetCode typical binary tree Golang solution

[226] Flip the binary tree

Leetcode-cn.com/problems/in…

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }

    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}
Copy the code

[116] Populates the right pointer of a binary tree node

Leetcode-cn.com/problems/po…

func connect(root *Node) *Node {
	if root == nil {
        return root
    }
    connectTwoNode(root.Left, root.Right)
    return root
}

func connectTwoNode(l, r *Node) {
    if l == nil || r == nil {
        return
    }
    l.Next = r
    connectTwoNode(l.Left, l.Right)
    connectTwoNode(l.Right, r.Left)
    connectTwoNode(r.Left, r.Right)
    return
}
Copy the code

[114] Expand the binary tree into a linked list

Leetcode-cn.com/problems/fl…

func flatten(root *TreeNode)  {
    if root == nil {
        return
    }

	flatten(root.Left)
	flatten(root.Right)

	currRight := root.Right
	root.Right = root.Left

	root.Left = nil
  // Find the bottom right node
	forroot.Right ! =nil {
		root = root.Right
	}

	root.Right = currRight
}
Copy the code

[101] Symmetric binary trees

Leetcode-cn.com/problems/sy…

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return false
    }
    return check(root.Left, root.Right)
}

func check(l, r *TreeNode) bool {

    if l == nil && r == nil {
        return true
    }
        
    if l == nil || r == nil {
        return false
    }

    ifl.Val ! = r.Val {return false
    }

    return check(l.Left, r.Right) && check(l.Right, r.Left)
}
Copy the code

[104] Maximum depth of binary trees

Leetcode-cn.com/problems/ma…

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    maxLeft := maxDepth(root.Left)
    maxRight := maxDepth(root.Right)

    var max int
    if maxLeft > maxRight {
        max = maxLeft
    } else {
        max = maxRight
    }

    return max + 1
}
Copy the code

[112] Sum of paths

Leetcode-cn.com/problems/pa…

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

	if root.Left == nil && root.Right == nil {
		return targetSum == root.Val
	}

    return hasPathSum(root.Left, targetSum - root.Val) || hasPathSum(root.Right, targetSum - root.Val)
}
Copy the code

[654] maximum binary tree

Leetcode-cn.com/problems/ma…

func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }

    maxIndex := 0    
    for i:=0; i<len(nums); i++{
        if nums[i] > nums[maxIndex] {
            maxIndex = i
        }
    }

    root := &TreeNode{Val:nums[maxIndex]}

    root.Left = constructMaximumBinaryTree(nums[:maxIndex])
    root.Right = constructMaximumBinaryTree(nums[maxIndex+1:)return root
}
Copy the code

[111] minimum depth of a binary tree

Leetcode-cn.com/problems/mi…

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

    return min(minDepth(root.Left), minDepth(root.Right)) + 1
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
Copy the code

[652] find duplicate subtrees

Leetcode-cn.com/problems/fi…

func findDuplicateSubtrees(root *TreeNode)[] *TreeNode {
	res, m := make([]*TreeNode, 0), make(map[string]int)
	traverse(root, &res, m)
	return res
}

func traverse(root *TreeNode, res *[]*TreeNode, m map[string]int) string {
	if root == nil {
		return ""
	}

	route := fmt.Sprintf("%s#%s#%s",
		root.Val,
		traverse(root.Left, res, m),
		traverse(root.Right, res, m))

	if val, ok := m[route]; ok {
		if val == 1 {
			*res = append(*res, root)
		}
	}
	m[route]++
	
	return route
}
Copy the code

[105] Construct a binary tree by traversing pre-order and middle-order sequences

Leetcode-cn.com/problems/co…

func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(inorder) == 0{
        return nil
    }

    root := &TreeNode{Val:preorder[0]}
    rootIndex := 0
    for i:=0; i<len(inorder); i++{
        if inorder[i] == root.Val {
            rootIndex = i
            break
        }
    }

    root.Left = buildTree(preorder[1:len(inorder[:rootIndex])+1], inorder[:rootIndex])
    root.Right = buildTree(preorder[len(inorder[:rootIndex])+1:], inorder[rootIndex+1:)return root
}
Copy the code

[106] Construct a binary tree by traversing sequences in middle and rear order

Leetcode-cn.com/problems/co…

func buildTree(inorder []int, postorder []int) *TreeNode {
    if len(inorder) == 0 || len(postorder) == 0 {
        return nil
    }
    root := &TreeNode{Val:postorder[len(postorder)- 1]}
    rootIndex := 0

    for i:=0; i<len(inorder); i++{
        if inorder[i] == root.Val{
            rootIndex = i
            break
        }
    }

    root.Left = buildTree(inorder[:rootIndex], postorder[:rootIndex])
    root.Right = buildTree(inorder[rootIndex+1:], postorder[rootIndex:len(postorder)- 1])
    return root
}
Copy the code

[236] The most recent common ancestor of binary trees

Leetcode-cn.com/problems/lo…

 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    if root.Val == p.Val || root.Val == q.Val {
        return root
    }
    
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    ifleft ! =nil&& right ! =nil {
        return root
    }
    if left == nil {
        return right
    } else {
        return left   
    }
}
Copy the code