力扣小记 791、99、103、109、112、113

791.自定义字符串排序

https://leetcode.cn/problems/custom-sort-string

思路:
用数组记录每个字符的位置，遍历s, 按照order的顺序自定义排序交换元素, 如果s里有order没有的元素默认位置置为0

func customSortString(order string, s string) string {
    dict := [26]int{}
    for i := range order {
        dict[order[i]-'a'] = i
    }
    cs := []byte(s)
    sort.Slice(cs, func(i, j int) bool {
        return dict[cs[i]-'a'] < dict[cs[j]-'a']
    })
    return string(cs)
}

99.恢复二叉搜索树

https://leetcode.cn/problems/recover-binary-search-tree

思路:
BST的特质, 中序遍历顺序是一个升序排序, 根据题意恰好两个节点的值被错误的交换, 可以在中序遍历中找到这两个节点然后交换

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var n1, n2 *TreeNode
var prev *TreeNode
func recoverTree(root *TreeNode)  {
    n1, n2 = nil, nil
    prev = &TreeNode{Val: math.MinInt}
    inorderTraverse(root)
    n1.Val, n2.Val = n2.Val, n1.Val
}

func inorderTraverse(root *TreeNode) {
    if root == nil {
        return
    }
    inorderTraverse(root.Left)
    if root.Val < prev.Val {
        if n1 == nil {
            n1 = prev
        }
        n2 = root
    }
    prev = root
    inorderTraverse(root.Right)
}

103.二叉树的锯齿形层序遍历

https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal

思路:
本质是一个层序遍历框架, 只不过在此基础上加了一个锯齿形层序遍历, 设置一个flag控制打印方向

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        LinkedList<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftOrRight = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> level = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (leftOrRight) {
                    level.addLast(cur.val);
                } else {
                    level.addFirst(cur.val);
                }
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            leftOrRight = !leftOrRight;
            res.add(level);
        }
        return res;
    }
}

109.有序链表转换二叉搜索树

https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree

思路:
这道题有很多种做法, 最先想到的还是先把链表转换成数组在去构建BST, 也可以先找到链表的中点再去构造BST

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedListToBST(head *ListNode) *TreeNode {
    nodes := []int{}
    for p := head; p != nil; p = p.Next {
        nodes = append(nodes, p.Val)
    }
    return build(nodes, 0, len(nodes)-1)
}

func build(nums []int, start, end int) *TreeNode {
    if start > end {
        return nil
    }
    mid := start + (end - start) / 2
    return &TreeNode{
        Val: nums[mid],
        Left: build(nums, start, mid-1),
        Right: build(nums, mid+1, end),
    }
}

112.路径总和

https://leetcode.cn/problems/path-sum

思路:
二叉树前序遍历, 维护进出节点的缓存值, 当节点是叶子节点时且缓存值等于目标值返回true, 反则false

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var found bool
var sum, target int
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    sum = 0
    found = false
    target = targetSum
    traverse(root)
    return found
}

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    sum += root.Val
    if root.Left == nil && root.Right == nil && sum == target {
        found = true
    }
    traverse(root.Left)
    traverse(root.Right)
    sum -= root.Val
}

113.路径总和Ⅱ

https://leetcode.cn/problems/path-sum-ii

思路:
和112相似，只不过需要记录多条路径, 仍然是前序遍历, 符合条件就记录起来。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var sum int
var res [][]int
func pathSum(root *TreeNode, targetSum int) [][]int {
    res = [][]int{}
    sum = 0
    if root == nil {
        return res
    }
    traverse(root, targetSum, []int{})
    return res
}

func traverse(root *TreeNode, targetSum int, path []int) {
    if root == nil {
        return
    }
    remain := targetSum - root.Val
    if root.Left == nil && root.Right == nil && remain == 0 {
        path = append(path, root.Val)
        temp := make([]int, len(path))
        copy(temp, path)
        res = append(res, temp)
        return
    }
    path = append(path, root.Val)
    traverse(root.Left, remain, path)
    traverse(root.Right, remain, path)
    path = path[:len(path)-1]
}

这里有个Golang的切片小陷阱, Golang的切片是指向底层数组的, 所以直接记录切片到res的话只是记录path的地址段, 当不发生扩容指向的是原地址，一旦发生扩容创建新的底层数组指向过去，地址是会动态改变的，所以要记录path的副本, 每次存path的副本保证数据的独立性