637.二叉树的层平均值
题目
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
示例 1:
输入:
3
/ \
9 20
/ \
15 7
输出: [3, 14.5, 11]
解释:
第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
注意：
节点值的范围在32位有符号整数范围内。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
层次遍历，得到每一层的节点总数和节点和总值计算平均值， 使用广度优先搜索。
代码
func averageOfLevels(root *TreeNode) []float64 {
res := []float64{}
if root == nil {
return res
}
cnt, sum := 0, 0 // 统计节点数和节点值和
q := []*TreeNode{root} // 切片当队列使用
for len(q) > 0 {
cnt = len(q)
sum = 0
for i := 0; i < cnt; i++ { // 遍历当前层的节点，并将下层节点添加到队列
tmp := q[0]
q = q[1:]
if tmp.Left != nil { // 左子树入队
q = append(q, tmp.Left)
}
if tmp.Right != nil { // 右子树入队
q = append(q, tmp.Right)
}
sum += tmp.Val
}
// 计算该层的平均值
res = append(res, float64(sum) / float64(cnt))
}
return res
} 513. 找树左下角的值
题目
给定一个二叉树，在树的最后一行找到最左边的值。
示例 1:
输入:
2
/ \
1 3
输出:
1
示例 2:
输入:
1
/ \
2 3
/ / \
4 5 6
/
7
输出:
7
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
使用深度优先搜索记录层数，每次遇到的第一个元素即是最左子树， 也可以通过广度优先搜索求解。
代码
var maxd, val int
func findBottomLeftValue(root *TreeNode) int {
maxd, val = 0, 0
dfs(root, 1)
return val
}
// 深度优先搜索
func dfs(root *TreeNode, d int) {
if root == nil {
return
}
if d > maxd {
maxd = d
val = root.Val
}
if root.Left != nil {
dfs(root.Left, d+1)
}
if root.Right != nil {
dfs(root.Right, d + 1)
}
} 144. 二叉树的前序遍历(非递归)
题目
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
前序遍历: 根->左->右。 使用栈模拟递归即可, 栈用go的切片进行模拟。
代码
func preorderTraversal(root *TreeNode) []int {
res := []int{}
stack :=[]*TreeNode{root} // 使用切片模拟栈
for len(stack) > 0 {
// 切片模拟出栈
s := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
if s == nil {
continue
}
res = append(res, s.Val)
// 右子树先入栈，保证先出栈的为左子树
stack = append(stack, s.Right)
stack = append(stack, s.Left)
}
return res
} 145.非递归实现二叉树的后序遍历
题目
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
后序遍历左->右->根, 等价于根->右->左遍历后结果的翻转。修改非递归实现的先序遍历代码的左右子树的入栈顺序，再将结果进行一次翻转即可得到结果。
代码
// 非递归实现二叉树的后序遍历
func postorderTraversal(root *TreeNode) []int {
// 非递归实现二叉树的后序遍历
res := []int{}
stack :=[]*TreeNode{root} // 使用切片模拟栈
for len(stack) > 0 {
// 切片模拟出栈
s := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
if s == nil {
continue
}
res = append(res, s.Val)
stack = append(stack, s.Left)// 左子树先入栈, 保证右子树先出站
stack = append(stack, s.Right)
}
res = reverses(res)
return res
}
// 切片翻转
func reverses(s []int) []int {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
return s
} 94.非递归实现二叉树的中序遍历
题目
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
二叉树的中序遍历， 左根右。
先将左子树全部进栈，然后取栈顶元素进行输出，接着右子树开始进栈。
代码
// 非递归实现二叉树的中序遍历
func inorderTraversal(root *TreeNode) []int {
res := []int{}
if root == nil {
return res
}
stack := []*TreeNode{}
cur := root
for cur != nil || len(stack) > 0 {
for cur != nil { // 先将左子树进栈
stack = append(stack, cur)
cur = cur.Left
}
// 取栈顶元素，即为根
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, node.Val)
// 遍历右子树
cur = node.Right
}
return res
} 669.修剪二叉搜索树
题目
给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
示例 1:
输入:
1
/ \
0 2
L = 1
R = 2
输出:
1
\
2
示例 2:
输入:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
输出:
3
/
2
/
1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trim-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
二叉搜索树是具有有以下性质的二叉树：
- 若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值。
- 若右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值。
- 左、右子树也分别为二叉搜索树。
修剪操作， 如当前节点的指针指向左子树，需要将左子树剪掉，将当前节点的指针指向左子树的子节点上，以此类推。
代码
func trimBST(root *TreeNode, L int, R int) *TreeNode {
if root == nil {
return nil
}
if root.Val > R {
return trimBST(root.Left, L, R)
}
if root.Val < L {
return trimBST(root.Right, L, R)
}
root.Left = trimBST(root.Left, L, R)
root.Right = trimBST(root.Right, L, R)
return root
} 230. 二叉搜索中第k小的元素
题目
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3
进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
二叉搜索树使用中序遍历, 第k个就是结果, 使用递归解法。
代码
// 求二叉搜索树第k小的元素
func kthSmallest(root *TreeNode, k int) int {
leftCnt := count(root.Left)
if leftCnt == k - 1 {
return root.Val
}
if leftCnt > k - 1 {
return kthSmallest(root.Left, k)
}
return kthSmallest(root.Right, k - leftCnt - 1)
}
func count(node *TreeNode) int {
if node == nil {
return 0
}
return 1 + count(node.Left) + count(node.Right)
} 235.二叉搜索树的最近公共祖先
题目
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5] 示例 1: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- 两个节点分别在左右子树，公共祖先是根节点；
- 两个节点都在左子树；
- 两个节点都在右子树；
代码
//求二叉搜索树的最近公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root.Val > p.Val && root.Val > q.Val { // 节点都在左子树
return lowestCommonAncestor(root.Left, p, q)
}
if root.Val < p.Val && root.Val < q.Val { // 节点都在右子树
return lowestCommonAncestor(root.Right, p, q)
}
return root
} 236.二叉树的最近公共祖先
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4] 示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 示例 2: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。 说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- 如果该节点就是子节点的其中之一，且能够通过该节点找到另一个子节点，那么这个节点就是最近公共祖先；
- 如果通过该节点不能找到两个子节点的，不是公共祖先，需要往上找；
- 如果通过该节点能找到两个子节点的，且分别位于其左子树或右子树上的，其就是最近公共祖先。
- 如果通过该节点能找到两个子节点的，且全部位于左子树或者右子树上的，是公共祖先，但不是最近的公共祖先，需要继续往下找。
代码
// 求二叉树的最近公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root == p || root == q {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left != nil && right != nil {
return root
}
if left != nil {
return left
}
return right
} 653.两数之和IV-输入BST
题目
给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
案例 1:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
输出: True
案例 2:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
输出: False
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题解
- 二叉查找树进行中序遍历，得到的序列是有序的，
- 再利用双指针进行求解即可。
代码
// 在二叉树中查找两个节点使之和等于k
func findTarget(root *TreeNode, k int) bool {
nums := []int{}
toArray(root, &nums)
i, j := 0, len(nums) - 1
for i < j {
sum := nums[i] + nums[j]
if sum == k {
return true
}
if sum < k {
i++
}else {
j--
}
}
return false
}
// 二叉查找树中序遍历后得到一个有序数组
func toArray(root *TreeNode, arr *[]int){
if root == nil {
return
}
toArray(root.Left, arr)
*arr = append(*arr, root.Val)
toArray(root.Right, arr)
}
京公网安备 11010502036488号