Facebook第一轮电面

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. }

复制代码

请教一下楼主，问project的时候侧重讲哪些方面比较好呢？
重点在语言还是项目内容呢？

markeey 发表于 2015-4-7 11:23
请教一下楼主，问project的时候侧重讲哪些方面比较好呢？
重点在语言还是项目内容呢？

语言你是只用了什么技术？主要是项目内容吧。。还会问你最challenge的点是啥 都很简单的。。关键在于你的coding部分

pandafolk 发表于 2015-4-8 00:30
语言你是只用了什么技术？主要是项目内容吧。。还会问你最challenge的点是啥 都很简单的。。关键在于你的 ...

challenge的这块要怎么回答？F家侧重哪些方面呢？
之前面的几家感觉说的不清楚，还浪费了很多时间。。。

markeey 发表于 2015-4-7 13:25
challenge的这块要怎么回答？F家侧重哪些方面呢？
之前面的几家感觉说的不清楚，还浪费了很多时间。。。

不知道。。我就随便说说

iterative 可以不用两个stack吧，用一个int随时update sum的值就可以了，走到底就把sum加在finalResult里面

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;
}