高德笔试高德笔试题 0321

笔试时间：2024年03月21日

历史笔试传送门：2023秋招笔试合集

第一题

题目

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

输入

root =[5,4,8,11,null,13,4,7,2,null,null,5,1]

targetSum = 22

输出

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

说明

树中节点总数在范围[0,5000]内 -1000<= Node.val<= 1000 -1000 <= targetSum <= 1000。

参考题解

二叉树路径和问题。先使用深度优先搜索（DFS）的方式遍历二叉树，如果当前节点是叶子节点，且目标和为 0，则说明找到了一条路径。找到所有路径和等于给定目标和的路径，并将其存储在二维向量ret 中返回。

C++：[此代码未进行大量数据的测试，仅供参考]

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;

    void dfs(TreeNode* root, int targetSum) {
        if (root == nullptr) {
            return;
        }
        path.emplace_back(root->val);
        targetSum -= root->val;
        if (root->left == nullptr && root->right == nullptr && targetSum == 0) {
            ret.emplace_back(path);
        }
        dfs(root->left, targetSum);
        dfs(root->right, targetSum);
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root, targetSum);
        return ret;
    }
};

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public void dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            ret.add(new ArrayList<>(path));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        path.remove(path.size() - 1);
    }

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return ret;
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        self.ret = []
        self.path = []

    def dfs(self, root, targetSum):
        if not root:
            return
        self.path.append(root.val)
        targetSum -= root.val
        if not root.left and not root.right and targetSum == 0:
            self.ret.append(self.path[:])
        self.dfs(root.left, targetSum)
        self.dfs(root.right, targetSum)
        self.path.pop()

    def pathSum(self, root, targetSum):
        self.dfs(root, targetSum)
        return self.ret