자바 이 진 트 리 의 몇 가지 재 귀적 및 비 재 귀적 실현 코드
8875 단어 자바 이 진 트 리비 귀속
중간 순서 로 옮 겨 다 닌 다.
후속 옮 겨 다 니 기
차례차례 편력 하 다
그림 2 진 트 리:
이 진 트 리 결점 구조
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val=x;
}
@Override
public String toString(){
return "val: "+val;
}
}
접근 함수
public void visit(TreeNode node){
System.out.print(node.val+" ");
}
앞 순 서 를 편력 하 다.그림 속 이 진 트 리 의 앞 순 서 는 6,20,1,4,5,8 로 나 타 났 다.
이 진 트 리 의 앞 순 서 는 뿌리 노드 를 옮 겨 다 니 고 왼쪽 노드 를 옮 겨 다 니 며 마지막 으로 오른쪽 노드 를 옮 겨 다 니 며 다음 과 같이 재 귀적 으로 사용 합 니 다.
/**
*
* */
public void preOrderRecursion(TreeNode node){
if(node==null) //
return;
visit(node);//
preOrderRecursion(node.left);//
preOrderRecursion(node.right);//
}
비 귀속:스 택 을 이용 하여 이 진 트 리 의 우선 순 서 를 재 귀적 으로 옮 겨 다 니 지 않 습 니 다.
/**
*
* */
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> resultList=new ArrayList<>();
Stack<TreeNode> treeStack=new Stack<>();
if(root==null) //
return resultList;
treeStack.push(root);
while(!treeStack.isEmpty()){
TreeNode tempNode=treeStack.pop();
if(tempNode!=null){
resultList.add(tempNode.val);//
treeStack.push(tempNode.right); //
treeStack.push(tempNode.left);//
}
}
return resultList;
}
업데이트:댓 글 에 재 귀적 이지 않 은 순서 로 옮 겨 다 니 는 것 을 이해 하지 못 한 다 는 사람 이 있 습 니 다.사실은 예 를 들 어 그림 을 그리 면 이해 할 수 있 습 니 다.상기 그림 에 있 는 이 진 트 리 를 예 로 들 면 먼저 6 을 스 택 에 넣 습 니 다.이때 List 는 비어 있 습 니 다.Stack 은 하나의 요소 6 만 있 습 니 다.while 순환 에 들 어가 서 스 택 꼭대기 에 List 를 넣 고 6 의 오른쪽 아이 와 왼쪽 아 이 를 스 택 에 넣 습 니 다.이때 Stack 은 스 택 밑 에서 스 택 꼭대기 까지 요 소 는 8,2 입 니 다.List 요 소 는 6 입 니 다.스 택 이 비어 있 지 않 기 때문에 while 순환 에 들 어가 면 스 택 꼭대기 2 를 팝 업 하고 2 를 List 에 추가 하 는 동시에 2 의 오른쪽 아이 와 왼쪽 아 이 를 각각 스 택 에 넣 습 니 다.이때 Stack 은 스 택 밑 에서 스 택 꼭대기 까지 의 요 소 는 8,4,0 이 고 List 의 요 소 는 6,2 입 니 다.스 택 이 비어 있 지 않 기 때문에 while 순환 에 다시 들 어 갑 니 다.순서대로 팝 업 0 은 List 에 들 어가 고 스 택 1,null 입 니 다.이때 Stack 은 스 택 밑 에서 스 택 꼭대기 까지 8,4,1,null 입 니 다.List 는 6,2,0,팝 업 null 은 비어 있 습 니 다.계속 1 을 팝 업 하면 됩 니 다.중간 순서 로 옮 겨 다 닌 다.
이 진 트 리 의 중간 순 서 를 옮 겨 다 니 는 것 은 왼쪽 노드 에 먼저 방문 한 다음 에 루트 노드 에 마지막 으로 오른쪽 노드 에 접근 하 는 것 이다.
귀속 방법 은 다음 과 같다.
/**
*
* */
public void preOrderRecursion(TreeNode node){
if(node==null) //
return;
preOrderRecursion(node.left);//
visit(node);//
preOrderRecursion(node.right);//
}
비 귀속:위의 그림 에서 이 진 트 리 의 순 서 는 0,1,2,4,5,6,8 입 니 다.
이 진 트 리 의 중간 순 서 는 다음 과 같 습 니 다.
먼저 루트 노드 를 창고 에 넣 고,
왼쪽 아이 가 내 려 가서 왼쪽 아 이 를 창고 에 넣 고 이 지점 에 왼쪽 아이 가 없 을 때 까지 이 지점 을 방문 합 니 다.만약 에 이 지점 에 오른쪽 아이 가 있다 면 오른쪽 아 이 를 창고 에 넣 고 왼쪽 아 이 를 찾 는 동작 을 반복 합 니 다.여기 서 결점 이 이미 방문 되 었 는 지 아 닌 지 를 판단 해 야 할 문제 가 있 습 니 다.
재 귀적 인 순서 로 옮 겨 다 니 지 않 습 니 다(효율 이 약간 낮 습 니 다).map(set 로 더 합 리 적 인 것 같 습 니 다)를 사용 하여 결점 이 방문 되 었 는 지 여 부 를 판단 합 니 다.
/**
*
* */
public List<Integer> inorderTraversalNonCur(TreeNode root) {
List<Integer> visitedList=new ArrayList<>();
Map<TreeNode,Integer> visitedNodeMap=new HashMap<>();//
Stack<TreeNode> toBeVisitedNodes=new Stack<>();//
if(root==null)
return visitedList;
toBeVisitedNodes.push(root);
while(!toBeVisitedNodes.isEmpty()){
TreeNode tempNode=toBeVisitedNodes.peek(); // peek pop
while(tempNode.left!=null){ // ,
if(visitedNodeMap.get(tempNode.left)!=null) // ( )
break;
toBeVisitedNodes.push(tempNode.left);
tempNode=tempNode.left;
}
tempNode=toBeVisitedNodes.pop();//
visitedList.add(tempNode.val);
visitedNodeMap.put(tempNode, 1);// map
if(tempNode.right!=null) //
toBeVisitedNodes.push(tempNode.right);
}
return visitedList;
}
Discuss 에서 더 간결 한 방법 을 알려 주 셨 어 요.
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur!=null || !stack.empty()){
while(cur!=null){
stack.add(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
return list;
}
뒤 순 서 를 옮 겨 다 닌 다.재 귀 코드 는 붙 이지 않 겠 습 니 다.
이전 비 재 귀 중 서 를 맵 으로 옮 겨 다 니 는 방법 으로 이해 한 후,후 서 를 옮 겨 다 니 면,우 리 는 이미 방문 한 결점 을 맵 으로 저장 할 수 있 습 니 다.후 서 를 옮 겨 다 니 는 것 은 왼쪽 아 이 를 먼저 방문 한 다음 에 오른쪽 아 이 를 방문 하여 마지막 으로 뿌리 결점 을 방문 하 는 것 입 니 다.
비 귀속 코드:
/**
*
* */
public List<Integer> postOrderNonCur(TreeNode root){
List<Integer> resultList=new ArrayList<>();
if(root==null)
return resultList;
Map<TreeNode,Integer> visitedMap=new HashMap<>();
Stack<TreeNode> toBeVisitedStack=new Stack<>();
toBeVisitedStack.push(root);
while(!toBeVisitedStack.isEmpty()){
TreeNode tempNode=toBeVisitedStack.peek(); // peek pop
if(tempNode.left==null && tempNode.right==null){ //
resultList.add(tempNode.val);
visitedMap.put(tempNode, 1);
toBeVisitedStack.pop();
continue;
}else if(!((tempNode.left!=null&&visitedMap.get(tempNode.left)==null )|| (tempNode.right!=null && visitedMap.get(tempNode.right)==null))){
//
resultList.add(tempNode.val);
toBeVisitedStack.pop();
visitedMap.put(tempNode, 1);
continue;
}
if(tempNode.left!=null){
while(tempNode.left!=null && visitedMap.get(tempNode.left)==null){//
toBeVisitedStack.push(tempNode.left);
tempNode=tempNode.left;
}
}
if(tempNode.right!=null){
if(visitedMap.get(tempNode.right)==null){//
toBeVisitedStack.push(tempNode.right);
}
}
}
return resultList;
}
Discuss 에서 어떤 사람 이'교묘 한'방법 을 제시 했다.즉,먼저 비슷 한 순서 로 옮 겨 다 니 고 뿌리 와 점 을 옮 겨 다 니 며 오른쪽 아이 가 마지막 에 왼쪽 아이(먼저 뿌리 와 점 을 찍 고 왼쪽 아이 가 마지막 에 오른쪽 아이)가 마지막 에 옮 겨 다 니 는 서열 을 역전 시 키 면 뒷 순 서 를 얻 을 수 있다.
public List<Integer> postorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
List<Integer> ret = new ArrayList<>();
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
ret.add(node.val);
stack.push(node.left);
stack.push(node.right);
}
}
Collections.reverse(ret);
return ret;
}
차례차례 편력 하 다층 차 를 옮 겨 다 니 는 것 도 너비 우선 검색 입 니 다.한 층 한 층 검색 합 니 다.재 귀적 코드 가 아 닌 것 은 다음 과 같 습 니 다.
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resultList=new ArrayList<>();
int levelNum=0;//
Queue<TreeNode> treeQueue=new LinkedList<>();
treeQueue.add(root);
while(!treeQueue.isEmpty()){
levelNum=treeQueue.size();
List<Integer> levelList=new ArrayList<>();
while(levelNum>0){
TreeNode tempNode=treeQueue.poll();
if(tempNode!=null){
levelList.add(tempNode.val);
treeQueue.add(tempNode.left);
treeQueue.add(tempNode.right);
}
levelNum--;
}
if(levelList.size()>0)
resultList.add(levelList);
}
return resultList;
}
자바 이 진 트 리 에 관 한 몇 가지 재 귀 와 비 재 귀 실현 코드 에 관 한 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 이 진 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
자바 이 진 트 리 의 몇 가지 재 귀적 및 비 재 귀적 실현 코드업데이트:댓 글 에 재 귀적 이지 않 은 순서 로 옮 겨 다 니 는 것 을 이해 하지 못 한 다 는 사람 이 있 습 니 다.사실은 예 를 들 어 그림 을 그리 면 이해 할 수 있 습 니 다.상기 그림 에 있 는 이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.