代码随想录算法训练营第十六天 | 654、617、700、98

算法
, , ,

654. 最大二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
    return build(nums, 0, len(nums)-1)
}

func build(nums []int, left, right int) *TreeNode {
    if left > right {
        return nil
    }
    maxIndex := left
    for i := left; i <= right; i++ {
        if nums[i] > nums[maxIndex] {
            maxIndex = i
        }
    }
    root := &TreeNode{Val: nums[maxIndex]}
    root.Left = build(nums, left, maxIndex-1)
    root.Right = build(nums, maxIndex+1, right)
    return root
}

617. 合并二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }
    // 合并当前节点值
    newNode := &TreeNode{Val: root1.Val + root2.Val}
    // 递归合并左右子树
    newNode.Left = mergeTrees(root1.Left, root2.Left)
    newNode.Right = mergeTrees(root1.Right, root2.Right)
    return newNode
}

700. 二叉搜索树中的搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == val {
        return root
    }
    if val < root.Val {
        return searchBST(root.Left, val)
    }
    return searchBST(root.Right, val)
}

98. 验证二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return helper(root, nil, nil)
}

func helper(node *TreeNode, lower, upper *int) bool {
    if node == nil {
        return true
    }
    val := node.Val
    if lower != nil && val <= *lower {
        return false
    }
    if upper != nil && val >= *upper {
        return false
    }
    return helper(node.Left, lower, &val) && helper(node.Right, &val, upper)
}