문제를 풀다--두 갈래 나무(2)
예lintcode 453.Flatten Binary Tree to Linked List https://www.lintcode.com/problem/flatten-binary-tree-to-linked-list/
traversal: 앞의 순서에 따라 구조를 변환하기 때문에 앞의 순서에 따라 귀속한다. 전역 변수는 루트 루트 노드이고 앞의 순서에 따라 구조의 변환을 한다.여기에 후효성 문제가 생길 수 있고 이차수 문제에 대해 우선 분치를 고려하여 해결하는 것도 나타난다.
divide conquer: 두 갈래 나무 문제는 분치법의 사고방식으로 이 나무가 문제의 답안에서 좌우 나무와 답안에서 어떤 관계가 있는지 고려하는 것이다.우선 좌우 트리가 결과를 되돌려 주었다면 뿌리를 어떻게 조작해야 할지 생각해 보자.왼쪽 나무의 끝 노드는 오른쪽 나무의 머리를 가리키고 뿌리의 왼쪽 나무는null이며 오른쪽 아이는 왼쪽 나무를 가리킨다.그래서 왼쪽 나무의 꼬리 노드를 알아야 한다.최종적으로 반환 값이 필요하지 않기 때문에recursion 함수의 반환 값은 끝 노드가 될 수 있습니다.왼쪽 나무 꼬리 노드가 비어 있지 않을 때 한 번 변환합니다.돌아올 때 우선 오른쪽 나무의 꼬리 노드가 비어 있는지 판단하고 비어 있지 않으면 돌아온다.그 다음에 왼쪽 트리 꼬리 노드가 판단하고 마지막으로 남은 상황은 루트로 돌아갑니다.recursion의 끝은 root==null입니다.
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void flatten(TreeNode root) {
helper(root);
}
public TreeNode helper(TreeNode root){
if(root == null)return null;
TreeNode leftLast = helper(root.left);
TreeNode rightLast = helper(root.right);
if(leftLast != null){
leftLast.right = root.right;
root.right = root.left;
root.left = null;
}
if(rightLast != null){
return rightLast;
}
if(leftLast != null){
return leftLast;
}
return root;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
