면접 문제 (8) 두 갈래 나무의 다음 노드
class TreeNode{
TreeNode left;
TreeNode right;
TreeNode parent;
int val;
}
사고방식: 구체적인 두 갈래 트리를 그려서 분석하면 알 수 있듯이 중서 역행 서열 중의 한 노드의 다음 노드의 위치는 이 노드가 오른쪽 노드에 영향을 받는지 여부이다. 만약에 이 노드가 오른쪽 노드가 존재한다면 다음 노드는 오른쪽 노드 중의 가장 왼쪽 노드이다.오른쪽 하위 트리가 존재하지 않으면 이 노드를 따라 위로 옮겨야 한다. 첫 번째가 부모 노드의 왼쪽 하위 노드인 것을 발견할 때까지 이 노드의 아버지 노드는 중차 옮겨다니는 서열의 다음 노드이다.
코드:
public TreeNode findNextInInSeq(TreeNode root, TreeNode node){
if(root == null || node == null)
return null;
//
if(node.right == null){
while(node.parent != null && node == node.parent.right)
node = node.parent;
return node.parent;
}
TreeNode right = node.right;
while(right.left != null)
right = right.left;
return right;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 프로그래머 면접에서의 다중 스레드 문제 요약wait ()/notify ()/notify All () 의 모든 방법을 호출할 때, 현재 라인이 이 대상의 자물쇠를 얻지 못하면, Illegal MonitorState Exception의 이상을 던집니다. Thre...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.