剑指 Offer 54. 二叉搜索树的第k大节点

遍历RNL（先Right再Node后Left）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func kthLargest(root *TreeNode, k int)  (res int) {
    var dfs func(*TreeNode)
    dfs = func(root *TreeNode) {
        if root == nil || k==0 {return}
        dfs(root.Right)
        k--
        if k == 0 {
            res = root.Val
            return
        }
        dfs(root.Left)
    }
    dfs(root)
    return res
}

剑指 Offer 34. 二叉树中和为某一值的路径

注意：深拷贝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func pathSum(root *TreeNode, target int) (ans [][]int) {
    path := []int{}
    var dfs  func(*TreeNode, int)
    dfs = func(node *TreeNode, left int){
        if node == nil{return}
        left -= node.Val
        path = append(path,node.Val)
        if node.Left==nil && node.Right==nil && left == 0{
            // 深拷贝
            ans = append(ans,append([]int(nil),path...))
        }
        dfs(node.Left,left)
        dfs(node.Right,left)
        defer func(){
            path = path[:len(path)-1]
        }()
    }

    dfs(root,target)
    return
}

剑指 Offer 28. 对称的二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil{
        return true
    }
    return recur(root.Left,root.Right)
}
func recur(L,R *TreeNode) bool{
    if L==nil && R==nil{
        return true
    }
    if L==nil && R!=nil || R==nil && L!=nil || L.Val != R.Val{
        return false
    }
    return recur(L.Left,R.Right) && recur(L.Right,R.Left)
}

剑指 Offer 27. 二叉树的镜像

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 mirrorTree(root *TreeNode) *TreeNode {
    if root == nil{
        return nil
    } 
    left := mirrorTree(root.Left)
    right := mirrorTree(root.Right)

    root.Left = right
    root.Right = left
    return root
}

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubStructure(A *TreeNode, B *TreeNode) bool {
    if B==nil || A==nil{
        return false
    }
    if A.Val==B.Val && judge(A,B){
        return true
    }

    return isSubStructure(A.Left,B) || isSubStructure(A.Right,B)
}

func judge(A *TreeNode, B *TreeNode) bool{
    if B==nil{
        return true
    }
    if A==nil && B!=nil || A.Val!=B.Val{
        return false
    }
    return judge(A.Left,B.Left) && judge(A.Right,B.Right)
}