트리 - 두 갈래 나무의 뒷차례 반복 (비귀속)
두 갈래 나무의 뒷차례는 비귀속 방법과 앞차례, 중간차례가 다르기 때문에 좀 번거롭다.
뿌리 결점은 왼쪽 아이와 오른쪽 아이가 방문한 후에야 방문할 수 있기 때문에 어떤 결점cur에 대해서도 먼저 창고에 넣는다.만약cur에 왼쪽 아이와 오른쪽 아이가 존재하지 않는다면 직접 방문할 수 있습니다.또는cur는 왼쪽 아이나 오른쪽 아이가 존재하지만 왼쪽 아이와 오른쪽 아이가 모두 방문하면 이 결점을 직접 방문할 수 있다.만약에 상술한 두 가지 상황이 아니라면cur의 오른쪽 아이와 왼쪽 아이를 순서대로 창고에 넣는다. 그러면 창고의 꼭대기 요소를 찾을 때마다 왼쪽 아이는 오른쪽 아이 앞에서 방문하고 왼쪽 아이와 오른쪽 아이는 모두 뿌리 결점 앞에서 방문한다.
코드는 다음과 같습니다.
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.*;
public class Solution {
private ArrayList<Integer> array=new ArrayList();
public ArrayList<Integer> postorderTraversal(TreeNode root) {
if(root == null)
return array;
Stack<TreeNode> stack=new Stack();
stack.push(root);
TreeNode pre=null;// array ；
while(!stack.empty())
{
TreeNode cur=stack.peek();
if(cur.left == null&&cur.right == null
||(pre!=null&&(pre == cur.left||pre == cur.right))
)// cur ;
{
array.add(cur.val);
stack.pop();
pre=cur;
}else// right left ， left ；
{
if(cur.right!=null)
{
stack.push(cur.right);
}
if(cur.left!=null)
{
stack.push(cur.left);
}
}
}
return array;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
