34题目描述:

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

解析:

1.初始化参数,结果列表res ,路径列表path,最后返回 res 即可。
2.backTrack函数:
递推参数:当前节点root,当前目标值target
终止条件:若节点root为空,则直接返回
3.递推工作:
路径更新:
将当前节点值 root.val 加入路径 path
目标值更新:target -= node.val
路径记录:当root为叶节点且路径和等于目标值,则将此路径path加入res
先序遍历:递归左/右子节点
路径恢复:向上回溯前,需要将当前节点从路径path中删除,即执行path.remove(path.size() - 1);

Java:

public List<List<Integer>> pathSum(TreeNode root, int target) {
        backTrack(root, target, new ArrayList<>());
        return res;
    }

    private List<List<Integer>> res = new ArrayList<>();
    private void backTrack(TreeNode node, int target, List<Integer> path) {
        if(node == null) {
            return;
        }
        path.add(node.val);
        target -= node.val;
        if(target == 0 && node.left == null && node.right == null) {
            res.add(new ArrayList<>(path));
        } else {
            backTrack(node.left, target, path);
            backTrack(node.right, target, path);
        }
        path.remove(path.size() - 1);
    }

JavaScript:

var pathSum = function(root, target) {
    const res = [];
    const path = [];
    root && backTrack(root, target, path, 0, res);
    return res;
};
function backTrack(node, target, path, sum, res) {
    path.push(node.val);
    sum += node.val;
    if(!node.left && !node.right && sum === target) {
        res.push([...path]);
    }
    node.left && backTrack(node.left, target, path, sum, res);
    node.right && backTrack(node.right, target, path, sum, res);
    path.pop();
}

36题目描述:

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

解析:

1.如果根节点为null,则返回null
2.递归根节点
3.然后使头尾节点相互连接,最后返回头节点
4.递归法中序遍历
(1)终止条件:当节点curr为空,代表越过叶节点,直接返回
(2)递归左子树,即dfs(curr.left)
(3)构建链表
当prev为空时,代表正在访问链表头节点,记为head;
当prev不为空时,修改双向节点引用,即prev.right = curr,curr.left = prev;
保存curr,更新prev = curr,即节点curr是后继节点的prev;
(4)递归右子树,即dfs(curr.right)

Java:

private Node prev, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) {
            return null;
        }
        dfs(root);
        head.left = prev;
        prev.right = head;
        return head;
    }

    private void dfs(Node curr) {
        if(curr == null) {
            return;
        }
        dfs(curr.left);
        curr.left = prev;
        if(prev == null) {
            head = curr;
        } else {
            prev.right = curr;
        }
        prev = curr;
        dfs(curr.right);
    }

JavaScript:

var treeToDoublyList = function(root) {
    if(root === null) {
        return null;
    }
    let head = null;
    let prev = null;
    dfs(root);
    head.left = prev;
    prev.right = head;
    return head;

    function dfs(curr) {
        if(curr === null) {
            return;
        }
        dfs(curr.left);
        curr.left = prev;
        if(prev === null) {
            head = curr;
        } else {
            prev.right = curr;
        }
        prev = curr;
        dfs(curr.right);
    }
};