. N-ary 트리 우편 주문 트래버스

590. N-ary Tree Postorder Traversa

난이도: 쉬움

주제: 스택, 트리, 깊이 우선 검색

n-항 트리의 루트가 주어지면 해당 노드 값의 후위 순회를 반환합니다.

Nary-Tree 입력 직렬화는 레벨 순서 탐색으로 표현됩니다. 각 하위 그룹은 null 값으로 구분됩니다(예 보기)

예 1:

• 입력: 루트 = [1,null,3,2,4,null,5,6]
• 출력: [5,6,3,2,4,1]

예 2:

• 입력: 루트 = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12 ,null,13,null,null,14]
• 출력: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

제약조건:

• 트리의 노드 수는 [0, 100⁴] 범위에 있습니다.
• -100 <= Node.val <= 100⁴
• n항 트리의 높이는 1000보다 작거나 같습니다.

후속 조치: 재귀적 솔루션은 간단합니다. 반복적으로 수행할 수 있습니까?

해결책:

재귀적 및 반복적으로 접근할 수 있습니다. 후속 조치에서는 반복적인 해결 방법이 요구되므로 이에 중점을 두겠습니다. 후위 순회는 하위 노드를 먼저 방문한 다음 상위 노드를 방문하는 것을 의미합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 590. N-ary Tree Postorder Traversal

<?php
//Definition for a Node.
class Node {
    public $val = null;
    public $children = [];

    public function __construct($val) {
        $this->val = $val;
    }
}

/**
 * @param Node $root
 * @return integer[]
 */
function postorder($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1:
$root1 = new Node(1);
$root1->children = [
    $node3 = new Node(3),
    new Node(2),
    new Node(4)
];
$node3->children = [
    new Node(5),
    new Node(6)
];

print_r(postorder($root1)); // Output: [5, 6, 3, 2, 4, 1]

// Example 2:
$root2 = new Node(1);
$root2->children = [
    new Node(2),
    $node3 = new Node(3),
    $node4 = new Node(4),
    $node5 = new Node(5)
];
$node3->children = [
    $node6 = new Node(6),
    $node7 = new Node(7)
];
$node4->children = [
    $node8 = new Node(8)
];
$node5->children = [
    $node9 = new Node(9),
    $node10 = new Node(10)
];
$node7->children = [
    new Node(11)
];
$node8->children = [
    new Node(12)
];
$node9->children = [
    new Node(13)
];
$node11 = $node7->children[0];
$node11->children = [
    new Node(14)
];

print_r(postorder($root2)); // Output: [2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10, 5, 1]
?>





  
  
  설명:




초기화:


스택을 생성하고 그 위에 루트 노드를 푸시합니다.
최종 주문 후 순회를 저장하기 위해 빈 배열 결과를 만듭니다.



순회:


스택에서 노드를 팝하고 결과 배열의 시작 부분에 해당 값을 삽입합니다.
모든 자식을 스택에 밀어 넣습니다.
스택이 빌 때까지 계속하세요.



결과:


결과 배열에는 루프가 완료된 후 후위 순서로 노드가 포함됩니다.




이 반복 접근 방식은 스택을 사용하고 일반적으로 재귀로 수행되는 프로세스를 역전시켜 사후 순서 순회를 효과적으로 시뮬레이션합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 . N-ary 트리 우편 주문 트래버스의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!