112. 路径总和

题目

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

1
2
3
4
5
6
7

 		 5
            / \
           4   8
          /   / \
         11  13  4
        /  \      \
       7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

112. 路径总和

思路

递归流程：

  • 子节点：
    • 为 nil 直接返回false
    • 为叶子结点，返回是否为 sum == 结点值
  • 遍历左子树，sum-结点值
  • 遍历右子树，sum-结点值

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

/**
 * 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]

1
2
3
4
5
6
7

  	  3
        /  \
    5		 1
    / \	 / \
  6	2	0	8
     /  \
    7    4

示例1:

1
2
3

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例2:

1
2
3

输入: 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 都位于左子树（或右子为空），则公共祖先由左子树中产生。反之则从右子树中产生

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

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],

1
2
3
4
5

    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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

借助队列实现（用切片模拟）

队列不为空的时候

  • 根节点的值计入结果，出队
  • 左子树或右子树不为空的话就入队
 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
31

/**
 * 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

题目

题目如上，要求结果是二维数组，即每一层放到一个数组里面

面试题32 - II. 从上到下打印二叉树 II

解答

主体思路同上，只是打印的时候，根据队列内的长度来分层

 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
31
32
33
34
35
36
37

/**
 * 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

题目

还是按层打印二叉树，这次要求是一层往左一层往右（之字型）

解答

大体思路同上面两题。

借助一个变量来存储往左还是往右，需要反向的时候对当前层的数组进行翻转即可

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

/**
 * 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 = 22

1
2
3
4
5
6
7

       5
      / \
     4   8
    /   / \
   11  13  4
  /  \    / \
7    2  5   1

返回:

1
2
3
4

  [
    [5,4,11,2],
     [5,8,4,5]
   ]

113. 路径总和 II

解答

深度优先搜索，到了根节点判断是否符合条件，符合就放入结果集

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

/**
 * 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]

1
2
3
4
5
6
7

        6
     /    \
    2      8
   / \    / \
  0   4   7  9
     / \
    3   5

示例 1:

1
2
3

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

1
2
3

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

235. 二叉搜索树的最近公共祖先

解答

题目给出的是 二叉搜索树，得重复利用这个条件。从节点的大小关系之间找规律

 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

/**
 * 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
2
3
4
5

	1					1->#
  /   \				  /   \
  2	   3			 2	-> 3->#
 / \	\			/ \	     \
4   5    7		   4-> 5  ->  7->#

1
2
3

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：

  • 树中的节点数小于 6000
  • -100 <= node.val <= 100

117. 填充每个节点的下一个右侧节点指针 II

解答

输入输出结果来看，就是层次遍历，然后依次往后指

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

/**
 * 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）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

例如,

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

# 给定二叉搜索树 和 插入的值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 新值和原始二叉搜索树中的任意节点值都不同

701. 二叉搜索树中的插入操作

解答

解法1: 递归 按照BST的性质来，根节点小于左子树大于右子树

中序遍历即可，顺序【根、左、右】

  • 比较 输入值 和 当前节点val 【根】

  • 输入值 >= val

    • 左子树为空，直接插入，return
    • 左子树非空，向左走 【左】

  • 输入值 < val

    • 右子树为空，直接插入，return
    • 右子树为空，向右走 【右】

解法2: 遍历 简述就是，派一个代表在树上去搜索，走到为null的时候停下来 把值赋给这个代表，return

 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
31
32
33
34
35
36
37
38
39
40
41
42

/**
 * 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
}