y*****e
发帖数: 712 | 1 第一题是print all path from root to leaf
比如tree是
A
B C
print AB, AC
这题用DFS还蛮好做的，如果用stack怎么做呢？
第二题有点像，给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问
了不递归怎么做
这题也是dfs好做，如果不递归的难点在于，每个treenode需要记录他的左子树的和，
右子书的和，再减去自己的node val. 一个stack好像不够，我是用了一个hashmap记录
每个node对应的左右子树的和，再用一个stack做post order traversal, 感觉挺麻烦
的，不知有什么巧妙的办法吗？
谢谢大家帮忙！ |
b**********5
发帖数: 7881 | 2 void printAllRootToLeaf(TreeNode root) {
}
void helper(TreeNode root, StringBuilder sb) {
if (root == null) return;
sb.append(root.val);
helper(root.left, sb);
helper(root.right, sb);
sb.remove(sb.length()-1);
}
=> to iterative+stack
void helper(TreeNode root) {
if (root == null) return;
while (root != null) {
sb.append(root.val);
stack.push(root);
root = root.left;
}
while (!stack.isEmpty()) {
TreeNode n = stack.pop();
n = n.right;
while (n != null) {
sb.append(n.val);
stack.push(n);
n = n.left;
}
print (sb);
sb.remove(sb.length()-1);
}
} |
C****t
发帖数: 53 | 3 I will try level-order for both.
Q1. level-order from the root
Q2. level-order from the bottom + hashtable
【在 y*****e 的大作中提到】
: 第一题是print all path from root to leaf
: 比如tree是
: A
: B C
: print AB, AC
: 这题用DFS还蛮好做的，如果用stack怎么做呢？
: 第二题有点像，给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问
: 了不递归怎么做
: 这题也是dfs好做，如果不递归的难点在于，每个treenode需要记录他的左子树的和，
: 右子书的和，再减去自己的node val. 一个stack好像不够，我是用了一个hashmap记录
|
b**********5
发帖数: 7881 | 4 返回每个点左右子树的和与自己值的差?
how should we return this? in a list? or just print it out?
void helper( ) {
if (root == null) return 0;
sum1 = helper(root.left);
sum2 = helper(root.right);
print(sum1+sum2-root.val);
return sum1+sum2+root.val;
} |
y*****e
发帖数: 712 | 5 牛肉姐别凶我，但你这个iterative的有bug吧，
比如3层的树，
3
2
1 4
如果delete character在print之后，print321, 324之后，要往3的右子树走的时候，2
还在sb里，因为只delete最后一个char.
【在 b**********5 的大作中提到】
: void printAllRootToLeaf(TreeNode root) {
: }
: void helper(TreeNode root, StringBuilder sb) {
: if (root == null) return;
: sb.append(root.val);
: helper(root.left, sb);
: helper(root.right, sb);
: sb.remove(sb.length()-1);
: }
: => to iterative+stack
|
e******n
发帖数: 144 | |
b**********5
发帖数: 7881 | 7 恩， 我fix不了了， 你fix吧。 我只想出把string也push到stack上, can u think
of something?
void printAllPath(Node root) {
Stack s1 = new Stack<>..
Stack s2 ...
s1.push(root); s2.push(root.val);
while (!s1.isEmpty()) {
Node n = s1.pop();
String s = s2.pop();
if (n.left == null && n.right == null) {
print s;
}
if (n.right != null) {
s1.push(n.right);
s2.push(s + n.right.val);
}
if (n.left != null) {
s1.push(n.left);
s2.push(s + n.left.val);
}
}
我觉得BFS， 也要两个queue？
，2
【在 y*****e 的大作中提到】
: 牛肉姐别凶我，但你这个iterative的有bug吧，
: 比如3层的树，
: 3
: 2
: 1 4
: 如果delete character在print之后，print321, 324之后，要往3的右子树走的时候，2
: 还在sb里，因为只delete最后一个char.
|
Q**w
发帖数: 41 | |
z***y
发帖数: 73 | 9 void printPath2(TreeNode* root)
{
if ( !root ) return;
std::stack st;
std::stack parents;
std::string prefix;
st.push(root);
while ( !st.empty() )
{
TreeNode* p = st.top();
st.pop();
if ( !p->left && !p->right ) {
std::cout << prefix << p->val << std::endl;
if ( st.empty() ) break;
while ( !parents.empty() && st.top() != parents.top()->right ) {
parents.pop();
prefix.erase(prefix.end() - 1);
}
}
else {
prefix.append(1, p->val);
parents.push(p);
if ( p->right ) st.push(p->right);
if ( p->left ) st.push(p->left);
}
}
}
【在 y*****e 的大作中提到】
: 第一题是print all path from root to leaf
: 比如tree是
: A
: B C
: print AB, AC
: 这题用DFS还蛮好做的，如果用stack怎么做呢？
: 第二题有点像，给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问
: 了不递归怎么做
: 这题也是dfs好做，如果不递归的难点在于，每个treenode需要记录他的左子树的和，
: 右子书的和，再减去自己的node val. 一个stack好像不够，我是用了一个hashmap记录
|
y******s
发帖数: 92 | 10 第一题用个wrapper class？
class Wrapper {
String root_until_current_node;
Node current;
}
把每一个wrapper装进stack？
第二题：
public int difference(Node root) {
if (root = null)
return 0;
if (root.left == null && root.right == null）
return root.val;
int left_diff = difference(root.left);
int right_diff = difference(root.right);
int res = root.val;
if (root.left != null)
res = res - (2*root.left.val-left_diff)
if (root.right != null)
res = res - (2*root.right.val-right_diff)
return res;
}
【在 y*****e 的大作中提到】
: 第一题是print all path from root to leaf
: 比如tree是
: A
: B C
: print AB, AC
: 这题用DFS还蛮好做的，如果用stack怎么做呢？
: 第二题有点像，给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问
: 了不递归怎么做
: 这题也是dfs好做，如果不递归的难点在于，每个treenode需要记录他的左子树的和，
: 右子书的和，再减去自己的node val. 一个stack好像不够，我是用了一个hashmap记录
|
t*****3
发帖数: 112 | 11 两个题的followup本质都是要求用postorder的stack解法
【在 y*****e 的大作中提到】
: 第一题是print all path from root to leaf
: 比如tree是
: A
: B C
: print AB, AC
: 这题用DFS还蛮好做的，如果用stack怎么做呢？
: 第二题有点像，给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问
: 了不递归怎么做
: 这题也是dfs好做，如果不递归的难点在于，每个treenode需要记录他的左子树的和，
: 右子书的和，再减去自己的node val. 一个stack好像不够，我是用了一个hashmap记录
|
a*********8
发帖数: 140 | 12 用recursion和post order的stack，做第一题：
class TreeNode2 {
char val;
TreeNode2 left;
TreeNode2 right;
TreeNode2(char val){
this.val = val;
}
}
public class Exercise2 {
public List pathRootToLeaf(TreeNode2 root){
List list = new ArrayList();
if (root == null){
return list;
}
List left = pathRootToLeaf(root.left);
List right = pathRootToLeaf(root.right);
if (left.size() == 0 && right.size() == 0){
list.add(root.val + "");
return list;
}
for (String s : left){
list.add(root.val + s);
}
for (String s : right){
list.add(root.val + s);
}
return list;
}
public List pathRootToLeaf2(TreeNode2 root){
List list = new ArrayList();
if (root == null){
return list;
}
Stack s = new Stack();
Stack s1 = new Stack();
Stack s2 = new Stack();
s.push(root);
s1.push(root.val + "");
while(!s.isEmpty()){
TreeNode2 cur = s.pop();
String curStr = s1.pop();
if (cur.left == null && cur.right == null){
s2.push(curStr);
}
if (cur.left != null){
s.push(cur.left);
s1.push(curStr + cur.left.val);
}
if (cur.right != null){
s.push(cur.right);
s1.push(curStr + cur.right.val);
}
}
while (!s2.isEmpty()){
list.add(s2.pop());
}
return list;
}
public static void main(String[] args){
TreeNode2 root = new TreeNode2('A');
root.left = new TreeNode2('B');
root.right = new TreeNode2('C');
root.left.left = new TreeNode2('D');
root.left.right = new TreeNode2('E');
root.right.right = new TreeNode2('F');
System.out.println(new Exercise2().pathRootToLeaf(root));
System.out.println(new Exercise2().pathRootToLeaf2(root));
} |
x*****0
发帖数: 452 | |
x*******9
发帖数: 138 | 14 第一题用BFS。（如果没有一定要用stack这个条件）
第二题用BFS先找到叶子节点，顺便找到每个节点的父节点。然后对于每个叶子节点，
两两Merge，一步一步向上推。
当然，这两种做法都是取巧的。不过，面试时开开无伤大雅的脑洞也不是不可以。 |
