讨论/求职面试/面试题目|讨论问题 阿里巴巴这道题难吗?真实笔试题。 另外可以内推/
面试题目|讨论问题 阿里巴巴这道题难吗?真实笔试题。 另外可以内推

讨论问题 阿里巴巴这道题难吗?真实笔试题

这道题在leetcode中应该算什么难度?
对这个问题一直没把握,发现实际面试中 不少同学被这道题拦住了。
大家帮忙看下,欢迎讨论,做出来可以发我邮箱, aric.lf@alibaba-inc.com

另外 实习+内推|阿里巴巴|淘宝技术|用户增长多个岗位|北京/杭州

题目

给定一个用“数组”表示的二叉树 以及 一个整数目标和 targetSum ,
找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
树节点的值 均为正整数 (有位同学很细心的发现了一个问题哈 如果是正整数 才可以作相关优化, 当然如果没说正整数,也有优化空间的)

示例 1

输入
tree = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
“注意 数组表示的方式 不是完全二叉树 用2n+1的方式定位是错误的 注意仔细读题”
表示树的结构

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

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

示例 2

输入:root = [1,2,3], targetSum = 5
输出:[]

public static List<List<Integer>> solve(List<Integer> tree, int target){

}

团队招聘 ———阿里巴巴淘系用户增长团队招人啦———

职位:Java/数据/算法/测试/前端/APP端/会员

BASE:杭州/北京

团队描述:

加入我们,增长不再神秘!!!!

用户增长一直是互联网公司最核心的诉求,也是最能影响公司财报的关键指标。

在对用户争夺进入白热化的时期,淘系用户增长团队正承担着捍卫电商主板块增长以及赋能集团创新板块增长的重要使命,我们将在最贴近用户的前线战场,用持续的技术创新来驱动阿里电商巨擎的稳步前行。我们正在建设完整的业界领先的用户增长中台,每日处理海量数据,系统过百万QPS。

用户增长技术团队是一支年轻开放的团队,倡导“增长黑客”极客氛围,在这里你将收获超大规模高并发的架构能力,洞悉用户增长最前沿的实践方法,在数字化时代具备最核心的竞争力。
感兴趣的发简历到我邮箱 aric.lf@alibaba-inc.com

14
共 96 个回复

如果是根结点到叶子结点就是简单题。
如果是任意结点到任意点(顺序还是从上到下)就是中等题。
如果是任意两个节点之间(无向无环图)路径和那就是困难题。

27

现在骗内推居然可以这样了

10

根节点到叶的和,扫描一遍树就行了,相当于
easy题吧

6

确实是发现有不少同学写错的。

8
该内容已被删除

并没有给错,他给的是BFS序列而不是一个完全二叉树。
要是完全二叉树那就更简单了。

3

遍历数组就好啦?假设下标从0开始。father节点下标为n,那么children节点下标分别为2n+1以及2n+2,遍历数组得到每个节点距离根节点距离。O(n)复杂度。计算就能得到路径,同时判断是否叶子节点只要子节点为null。

3

这题是将两道题合并到一起了,先将数组反序列化成树,再遍历去找targetSum

  1. 剑指 Offer 37. 序列化二叉树
  2. 剑指 Offer 34. 二叉树中和为某一值的路径
3

这数组就是完全二叉树了,i的左节点是2i+1,右节点是2i+2,父节点是(i-1)/2,不用建树,直接dfs(0)求和就可以了

2

DFS,数组形式(在开头补充一个空元素)遍历树,i从1开始遍历,则左子节点是i2,右子节点是i2+1

2

思路就是 BFS 建树,然后DFS 求答案

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
#include <cstdio>
#include <map>
#include <set>
using namespace std;
struct Node {
    int val;
    Node* left,*right;
    Node(int v) {
        val = v;
        left=right = 0;
    }
};
//dfs 遍历
//记录路径
vector<int> step;

//最终答案
vector<vector<int>> ret;
void dfs(Node* r, int target,int curtotal) {
    if (r) {
        step.push_back(r->val);
        //叶并且判断条件
        if (r->left == 0 && r->right == 0 && (curtotal+r->val)==target) {
            ret.push_back(step);
            step.pop_back();
            return;
        }
        dfs(r->left, target, curtotal+r->val);
        dfs(r->right, target, curtotal+r->val);
        step.pop_back();
    }
}
void fun(vector<int> tree,int target) {
    //build tree
    queue<Node*> q;
    int i = 0;
    Node* root = new Node(tree[i++]);
    q.push(root);
    int nodecnt = tree.size();
    while (!q.empty()) {
        int ln = q.size();
        for (int j=0; j < ln; j++) {
            Node* curNode = q.front();
            q.pop();
            if (i<nodecnt) {
                int lf = tree[i++];
                if (lf != -1) {
                    curNode->left = new Node(lf);
                    q.push(curNode->left);
                }
            }
            if (i< nodecnt) {
                int rg = tree[i++];
                if (rg != -1) {
                    curNode->right = new Node(rg);
                    q.push(curNode->right);
                }
            }
        }
    }
    //
    dfs(root, target,0);


    //
    for (auto& r : ret) {
        for (auto& num : r) {
            cout << num << "-";
        }
        cout << endl;
    }
}
int main()
{
    //为了方便null用-1代替,默认结点没有-1,懒得分解字符串了
    vector<int> vec{ 5,4,8,11,-1,13,4,7,2,-1,-1,5,1 };
    fun(vec, 22);
    return 0;
}
1