[이 진 트 리 검색] 면접 문제 17.12. BiNode.

5709 단어 Leetcode
제목.
이 진 트 리 데이터 구조 TreeNode 는 단 방향 링크 (그 중에서 left 가 비어 있 고 right 는 다음 링크 노드) 를 표시 할 수 있 습 니 다.이 진 트 리 를 단 방향 링크 로 바 꾸 는 방법 을 실현 합 니 다. 이 진 트 리 의 특성 에 부합 되 어야 합 니 다. 전환 작업 은 원래 의 주소, 즉 원 초적 인 이 진 트 리 에서 직접 수정 해 야 합 니 다.
전환 후의 단 방향 링크 의 머리 노드 를 되 돌려 줍 니 다.
주의: 본 문 제 는 원래 의 문제 에 비해 약간 변경 되 었 습 니 다.
예시:
[4,2,5,1,3,null,6,0][0,null,1,null,2,null,3,null,4,null,5,null,6]

출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/binode-lcci 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
이 진 트 리 검색 의 중요 한 특징: 중 서 는 질서 가 있 습 니 다. 이 성질 을 알 고 있 으 면 이 문 제 는 중 서 를 옮 겨 다 니 며 풀 면 됩 니 다. 새 임시 변수 head, tail 는 이 진 트 리 를 구축 하 는 데 사 용 됩 니 다. 중 서 를 옮 겨 다 니 는 과정 에서 노드 간 의 연결 관 계 를 수정 하고 중 서 를 옮 길 때 tail 의 오른쪽 아 이 를 현재 노드 로 가리 키 고 tail현재 노드 로 내 려 가 왼쪽 아 이 를 비 웁 니 다.
// Definition for a binary tree node.
class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

class Solution {
	public TreeNode head, tail;

	public TreeNode convertBiNode(TreeNode root) {
		head = new TreeNode(-1);
		tail = head;
		InOrder(root);
		return head.right;
	}

	public void InOrder(TreeNode root) {
		if (root == null)
			return;
		InOrder(root.left);
		tail.right = root;
		tail = root;
		tail.left = null;
		InOrder(root.right);
	}
}

좋은 웹페이지 즐겨찾기