117. Populating Next Right Pointers in Each Node II
3866 단어 right
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
For example,Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
Hide Tags
Tree Depth-first Search
링크:http://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
문제:
마찬가지로 DFS입니다.다음 문제와 달리 주어진 입력은 완전한 두 갈래 나무가 아니기 때문에 합리적인 넥스트 값이 존재하는지 판단하기 위해 조건을 넣어야 한다.또한 왼쪽 노드와 오른쪽 노드의 유효성도 검증해야 한다.마지막으로 오른쪽 노드를 연결한 다음에 왼쪽 노드를 연결합니다.
Time Complexity - O(n), Space Complexity - O(1).
public class Solution {
public void connect(TreeLinkNode root) {
if(root == null)
return;
TreeLinkNode node = root.next;
while(node != null){
if(node.left != null){
node = node.left;
break;
} else if(node.right != null){
node = node.right;
break;
}
node = node.next;
}
if(root.right != null){
root.right.next = node;
if(root.left != null)
root.left.next = root.right;
} else {
if(root.left != null)
root.left.next = node;
}
connect(root.right);
connect(root.left);
}
}테스트:
Reference:
http://www.cnblogs.com/springfor/p/3889327.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
3월 3일 [Go_deep]Populating Next Right Pointers in Each Node원제: 간단한 체인 트리는 Next 노드 정보를 증가시켜 구덩이가 없습니다.그래도 WA를 두 번이나 했는데 주문이 있어서 계속 해요. 그리고 leetcode는 모두 150문제예요. 2주 동안 생각해 봐요. 빨리 해야...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
