u****g
发帖数: 402 | 1 一个二叉树，怎么样做到每个节点指向同level的下一个节点 | a*********0
发帖数: 2727 | 2 traverse the tree, mark the height of each node, traverse again, find the
first next node with the same height
【在 u****g 的大作中提到】
: 一个二叉树，怎么样做到每个节点指向同level的下一个节点
| q*****9
发帖数: 85 | | h**********d
发帖数: 4313 | 4 1.如果是full tree，可以用递归
2.如果不是full tree，笨办法用level-order traversal遍历，同时把当前节点next指
向queue.peek(),复杂度O(N)
写个java版本
void populate(TreeNode root){
if(root == null)return;
Queue queue = new Queue();
queue.put(root);
Node node;
int thisLevel = 1; int nextLevel = 0;
while(!queue.isEmpty()){
node = queue.pop();
thisLevel--;
if(thisLevel != 0){
node.setNextRight(queue.peek());
}
if(node.getLeft() != null){
queue.put(node.getLeft());
nextLevel++;
}
if(node.getRight() != null{
queue.put(node.getRight());
nextLevel++;
}
if(thisLevel == 0){
thisLevel = nextLevel;
nextLevel = 0;
}
}
}
【在 u****g 的大作中提到】
: 一个二叉树，怎么样做到每个节点指向同level的下一个节点
|
|
