leetcode_树合集
112. 路径总和
题目
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1返回
true, 因为存在目标和为 22 的根节点到叶子节点的路径5->4->11->2。112. 路径总和
思路
递归流程：
- 子节点：
- 为 nil 直接返回false
- 为叶子结点，返回是否为 sum == 结点值
- 遍历左子树，
sum-结点值 - 遍历右子树，
sum-结点值
解答
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func hasPathSum(root *TreeNode, sum int) bool {
// 出口1
if root == nil {
return false
}
// 出口2
if root.Left == nil && root.Right == nil {
return sum == root.Val
}
return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}
236. 二叉树的最近公共祖先
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
3 / \ 5 1 / \ / \ 6 2 0 8 / \ 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答
-
如果p, q 分别位于左、右子树，则根即为要找的节点
-
如果p, q 都位于左子树（或右子为空），则公共祖先由左子树中产生。反之则从右子树中产生
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// 出口
if p == root || q == root || root == nil {
return root
}
left, right := lowestCommonAncestor(root.Left, p, q), lowestCommonAncestor(root.Right, p, q)
// 左子树都为空了，从右子树上找
if left == nil {
return right
}
// 右子树都为空了，从左子树上找
if right == nil {
return left
}
return root
}
// 执行用时 :12 ms, 在所有 Go 提交中击败了92.99%的用户
// 内存消耗 :7.1 MB, 在所有 Go 提交中击败了96.26%的用户
面试题32 - I. 从上到下打印二叉树
题目
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如: 给定二叉树: [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7返回：[3,9,20,15,7]
提示：
节点总数 <= 1000
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答
借助队列实现（用切片模拟）
队列不为空的时候
- 根节点的值计入结果，出队
- 左子树或右子树不为空的话就入队
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) []int {
if root == nil {
return []int{}
}
ret := []int{}
que := []*TreeNode{}
que = append(que, root)
for len(que) > 0 {
node := que[0]
ret = append(ret, node.Val)
que = que[1:]
if node.Left != nil {
que = append(que, node.Left)
}
if node.Right != nil {
que = append(que, node.Right)
}
}
return ret
}
// 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户
// 内存消耗 :2.7 MB, 在所有 Go 提交中击败了100.100%的用户
面试题32 - II. 从上到下打印二叉树 II
题目
题目如上，要求结果是二维数组，即每一层放到一个数组里面
解答
主体思路同上，只是打印的时候，根据队列内的长度来分层
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
ret := [][]int{}
que := []*TreeNode{}
que = append(que, root)
for len(que)>0 {
row := []int{}
for _ = range que {
front := que[0]
que = que[1:]
row = append(row, front.Val)
if front.Left != nil {
que = append(que, front.Left)
}
if front.Right != nil {
que = append(que, front.Right)
}
}
ret = append(ret, row)
}
return ret
}
// 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户
// 内存消耗 :2.8 MB, 在所有 Go 提交中击败了100.100%的用户
面试题32 - III. 从上到下打印二叉树 III
题目
还是按层打印二叉树，这次要求是一层往左一层往右（之字型）
解答
大体思路同上面两题。
借助一个变量来存储往左还是往右，需要反向的时候对当前层的数组进行翻转即可
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
ret := [][]int{}
que := []*TreeNode{}
que = append(que, root)
var way bool // false往右，true往左
for len(que) > 0 {
row := []int{}
for _ = range que {
front := que[0]
row = append(row, front.Val)
que = que[1:]
if front.Left != nil {
que = append(que, front.Left)
}
if front.Right != nil {
que = append(que, front.Right)
}
}
if way {
row = reverse(row)
}
way = !way
ret = append(ret, row)
}
return ret
}
func reverse(arr []int) []int {
l := len(arr)-1
for i:=0; i < l; i++ {
arr[i], arr[l] = arr[l], arr[i]
l--
}
return arr
}
// 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户
// 内存消耗 :2.8 MB, 在所有 Go 提交中击败了100.100%的用户
113. 路径总和 II
题目
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和
sum = 225 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:
[ [5,4,11,2], [5,8,4,5] ]
解答
深度优先搜索，到了根节点判断是否符合条件，符合就放入结果集
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, sum int) (ret [][]int) {
var (
path []int
dfs func(*TreeNode, int)
)
dfs = func(node *TreeNode, spare int) {
if node == nil {
return
}
// 根节点事务：符合条件就加入结果集
spare -= node.Val
path = append(path, node.Val)
defer func(){ path = path[:len(path)-1] }()
// 满足条件：消耗完 + 到了叶子节点
if spare == 0 && root.Left == nil && root.Right == nil {
// 这里不能直接 append(ret, path)，因为path是指针，最后ret的值会随着path改变
ret = append(ret, append([]int(nil), path...))
return // 满足条件直接退出
}
// 不满足条件，继续搜索
dfs(node.Left, spare)
dfs(node.Right, spare)
}
dfs(root, sum)
return ret
}
// dfs过程：根左右
// dfs = func(node *TreeNode, spare int) {
// if node == nil {
// return
// }
// // 处理根节点的事情
// dfs(node.Left, spare) // 左子树
// dfs(node.Right, spare) // 右子树
// }
// 执行用时：4 ms, 在所有 Go 提交中击败了93.80%的用户
// 内存消耗：4.7 MB, 在所有 Go 提交中击败了50.92%的用户
235. 二叉搜索树的最近公共祖先
题目
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树:
root = [6,2,8,0,4,7,9,null,null,3,5]6 / \ 2 8 / \ / \ 0 4 7 9 / \ 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, 因为根据定义最近公共祖先节点可以为节点本身。
解答
题目给出的是 二叉搜索树，得重复利用这个条件。从节点的大小关系之间找规律
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// 当前节点值 大于 p,q, 此节点在pq右侧的分支上 [比如这里的6和0,4]
// 6
// / \
// 2 8
// / \
// 0 4
if root.Val > p.Val && root.Val > q.Val {
// 从左子树上找
lowestCommonAncestor(root.Left, p, q)
}
if root.Val < p.Val && root.Val < q.Val {
// 从右子树上找
lowestCommonAncestor(root.Right, p, q)
}
// 否则符合条件 因为 当前节点同时在 pq 的左边和右边，那么肯定就是公共祖先
return root
}
117. 填充每个节点的下一个右侧节点指针 II
题目
给定一个二叉树
struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
1 1-># / \ / \ 2 3 2 -> 3-># / \ \ / \ \ 4 5 7 4-> 5 -> 7->#输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。提示：
- 树中的节点数小于
6000-100 <= node.val <= 100
解答
输入输出结果来看，就是层次遍历，然后依次往后指
/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Next *Node
* }
*/
func connect(node *Node) *Node {
if node == nil {
return nil
}
var que = []*Node{node}
for len(que) > 0 {
l := len(que)
for i := 0; i < l; i++ {
head := que[0] // 队头
que = que[1:] // 出队
if i < l-1 {
head.Next = que[0] // 往后指
}
// 继续入队
if head.Left != nil {
que = append(que, head.Left)
}
if head.Right != nil {
que = append(que, head.Right)
}
}
}
return node
}
// case
//var (
// n5 = &Node{Val: 5}
// n1_1 = &Node{Val: 1}
// n1_2 = &Node{Val: 1, Left: n5, Right: n1_1}
// n6 = &Node{Val: 6}
// n3 = &Node{Val: 3, Right: n6}
// n8 = &Node{Val: 8}
// n_1 = &Node{Val: -1, Right: n8}
// n2 = &Node{Val: 2, Left: n1_1}
// n4 = &Node{Val: 4, Left: n3, Right: n_1}
// n0 = &Node{Val: 0, Left: n2, Right: n4}
//)
// 执行用时：4 ms, 在所有 Go 提交中击败了76.10%的用户
// 内存消耗：6.2 MB, 在所有 Go 提交中击败了10.90%的用户
701. 二叉搜索树中的插入操作
题目
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
例如,
# 给定二叉搜索树 和 插入的值5: 4 / \ 2 7 / \ 1 3 # 你可以返回这个二叉搜索树: 4 / \ 2 7 / \ / 1 3 5 # 或者这个树也是有效的: 5 / \ 2 7 / \ 1 3 \ 4提示：
给定的树上的节点数介于
0和10^4之间 每个节点都有一个唯一整数值，取值范围从0到10^8-10^8 <= val <= 10^8新值和原始二叉搜索树中的任意节点值都不同
解答
解法1: 递归 按照BST的性质来，根节点小于左子树大于右子树
中序遍历即可，顺序【根、左、右】
-
比较 输入值 和 当前节点
val【根】 -
输入值 >=
val- 左子树为空，直接插入，
return - 左子树非空，向左走 【左】
- 左子树为空，直接插入，
-
输入值 <
val- 右子树为空，直接插入，
return - 右子树为空，向右走 【右】
- 右子树为空，直接插入，
解法2: 遍历 简述就是，派一个代表在树上去搜索，走到为null的时候停下来 把值赋给这个代表，return
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil { // 为空也插入，不是返回nil
return &TreeNode{
Val: val,
}
}
var insert func(*TreeNode)
insert = func(p *TreeNode) {
if p == nil {
return
}
// 根节点
if val <= p.Val {
if p.Left == nil {
p.Left = &TreeNode{
Val: val,
}
return
}
insert(p.Left) // 左子树
} else {
if p.Right == nil {
p.Right = &TreeNode{
Val: val,
}
return
}
insert(p.Right) // 右子树
}
}
insert(root)
return root
}
