【Leetcode】Populating Next Right Pointers in Each Node II
제목:
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:
You may only use constant extra space.
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
생각:
1、"Populating Next Right Pointers in Each Node"를 사용합니다.의 알고리즘은 여전히 유효하지만 공간 복잡도는 O(n)
알고리즘 1:
public void connect(TreeLinkNode root) {
List<List<TreeLinkNode>> lists = levelOrder(root);
for (List<TreeLinkNode> list : lists) {
for (int i = 0; i < list.size() - 1; i++) {
list.get(i).next = list.get(i + 1);
}
list.get(list.size() - 1).next = null;
}
}
/**
*
*/
public List<List<TreeLinkNode>> levelOrder(TreeLinkNode root) {
int height = heightTree(root);
List<List<TreeLinkNode>> lists = new ArrayList<List<TreeLinkNode>>();
for (int i = 1; i <= height; i++) {
List<TreeLinkNode> list = new ArrayList<TreeLinkNode>();
list = kLevelNumber(root, 1, list, i);
lists.add(list);
}
return lists;
}
/***
* kk ，height
*/
public List<TreeLinkNode> kLevelNumber(TreeLinkNode p, int height, List<TreeLinkNode> list, int kk) {
if (p != null) {
if (height == kk) {
list.add(p);
}
list = kLevelNumber(p.left, height + 1, list, kk);
list = kLevelNumber(p.right, height + 1, list, kk);
}
return list;
}
public int heightTree(TreeLinkNode p) {
if (p == null)
return 0;
int h1 = heightTree(p.left);
int h2 = heightTree(p.right);
return h1 > h2 ? h1 + 1 : h2 + 1;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
