Facebook第一轮电面

很传统：先介绍简历 + 做题 + 问问题。
题目1：求二叉树所有从根开始到叶子的所有路径和。
题目2：不能用递归，完成以上题目。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

终”。。。写总收到感觉很损人品啊。。。。。。哪有总。。。求签证过了吧。。

Recursive的话就是典型的 DFS，中间结果的 sum 都当做一个参数传到下一层递归。
如果要 Iterative 的话就是把 DFS 写成 Non-recursive的，也就是用 stack 实现。这时需要保存中间结果的 sum，用另一个 stack 可以解决，楼上所说的用一个 int 保存中间结果，我没有想出来怎么实现，因为在遇到叶子节点的时候，不知道要在 sum 里减掉多少回退到上一层，可能回退的层数不是1。

粗略写的代码如下：
#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};

void pathSumRecHelper(TreeNode *root, int sum, int &res) {
  if (root->left == NULL && root->right == NULL) {
    sum += root->val;
    res += sum;
    return;
  }

  if (root->left != NULL) pathSumRecHelper(root->left, sum + root->val, res);
  if (root->right != NULL) pathSumRecHelper(root->right, sum + root->val, res);
}

int pathSumRec(TreeNode *root) {
  if (root == NULL) return 0;
  int res = 0;
  pathSumRecHelper(root, 0, res);
  return res;
}

int pathSumItr(TreeNode *root) {
  if (root == NULL) return 0;
  stack<TreeNode *> node_stack;
  stack<int> sum_stack;
  int res = 0;

  node_stack.push(root);
  sum_stack.push(root->val);

  while (!node_stack.empty()) {
    TreeNode *node = node_stack.top();
    int sum = sum_stack.top();
    node_stack.pop();
    sum_stack.pop();
    if (node->left == NULL && node->right == NULL) {
      res += sum;
    }

    if (node->left != NULL) {
      node_stack.push(node->left);
      sum_stack.push(sum + node->left->val);
    }

    if (node->right != NULL) {
      node_stack.push(node->right);
      sum_stack.push(sum + node->right->val);
    }
  }

  return res;
}

int main(int argc, char const *argv[]) {
  TreeNode *root = new TreeNode(1);
  TreeNode *n1 = new TreeNode(2);
  TreeNode *n2 = new TreeNode(5);
  TreeNode *n3 = new TreeNode(3);
  TreeNode *n4 = new TreeNode(4);

  root->left = n1;
  root->right = n2;
  n1->left = n3;
  n1->right = n4;

  int sum = pathSumItr(root);
  cout << sum << endl;
}

为什么我觉得non-recursive的方法更好想。。。我感觉我被绕进去了，我写的recursive方法是先得到所有的path在加起来==特别冗余
求指导如何简单的就直接得到sum……

1. public static List<List<Integer>> getAllPathSum(TreeNode root) {
   
2.         List<List<Integer>> rst = new ArrayList<List<Integer>>();
   
3. 
   
4.         helper(rst, new ArrayList<Integer>(), root);
   
5.         return rst;
   
6.     }
   
7. 
   
8.     public static void helper(List<List<Integer>> rst, ArrayList<Integer> list,
   
9.                        TreeNode root) {
   
10.         if (root == null) {
    
11.             return;
    
12.         }
    
13.         list.add(root.val);
    
14.         if (root.left == null && root.right == null) {
    
15.             rst.add(new ArrayList<Integer>(list));
    
16.         }
    
17.         helper(rst, list, root.left);
    
18.         helper(rst, list, root.right);
    
19.         list.remove(list.size() - 1);
    
20.     }

复制代码

sanguine 发表于 2015-3-15 16:58
为什么我觉得non-recursive的方法更好想。。。我感觉我被绕进去了，我写的recursive方法是先得到所有的path ...

额，你这么写的话确实。。
可以这样呀~

1. public class Solution {
   
2.     public int sumNumbers(TreeNode root) {
   
3.         return dfs(root, 0);
   
4.     }
   
5.    
   
6.     private int dfs(TreeNode root, int prev) {
   
7.         if (root == null) {
   
8.             return 0;
   
9.         }
   
10.         
    
11.         int sum = prev + root.val;
    
12.         if (root.left == null && root.right == null) {
    
13.             return sum;
    
14.         }
    
15.         
    
16.         return dfs(root.right, sum) + dfs(root.left, sum);
    
17.     }
    
18. }

复制代码

有不明白的大家请猛烈问我啊~~~
另外隔了四天才收到通过。。。可能是自己太水了

楼主通过了是指要去onsite了吗？恭喜啊！

请问follow up的第二问怎么实现呢？

lsycody 发表于 2015-3-11 16:06
楼主通过了是指要去onsite了吗？恭喜啊！

请问follow up的第二问怎么实现呢？

用两个stack实现呀~~
一个存储结点，另一存储和
比如
       1
    2     5
3     4
第一次，root入stack
node【1，
sum【1，
然后pop栈顶元素，push其儿子，我这里习惯先push右边的，这样输出就是先输出左边的~：
node【5，2
sum【6，3
然后取出结点2，和它的sum，再push儿子
node【5，4，3
sum【6，7，6
然后到3了，发现是叶子，那么pop出来直接输出：6
node【5，4
sum【6，7
然后到4了。发现又是叶子，那么再次pop出来直接输出咯：7
node【5
sum【6
终于到5了，还是叶子，那么就输出咯：6
完毕~~~~

最后输出一个int = 6 + 7 + 6 = 19~~~~

恩~~祝你onsite顺利！

不知道题目是不是我理解错的 leetcode上有个类似题目 也是求和

比如root是1 两个儿子是2和3 那么就输出12+13=25

ryuichist 发表于 2015-3-11 16:54
比如root是1 两个儿子是2和3 那么就输出12+13=25

不一定出原题啊。。。另外是哪个题目啊 求链接~~

第二问用后续或者level order 都可以解