. 이진 트리 후위 순회

145. 이진 트리 후위 순회

난이도: 쉬움

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

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

예 1:

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

예 2:

• 입력: 루트 = []
• 출력: []

예 3:

• 입력: 루트 = [1]
• 출력: [1]

제약조건:

• 트리의 노드 수는 [0, 100] 범위에 있습니다.
• -100 <= Node.val <= 100

해결책:

스택에 반복적 접근 방식을 사용할 수 있습니다. 후위 순회는 왼쪽, 오른쪽, 루트 순서를 따릅니다.

이 솔루션을 PHP로 구현해 보겠습니다. 145. 이진 트리 후위 순회

val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}
/**
* @param TreeNode $root
* @return Integer[]
*/
function postorderTraversal($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

// Example 1
$root1 = new TreeNode(1);
$root1->right = new TreeNode(2);
$root1->right->left = new TreeNode(3);
print_r(postorderTraversal($root1)); // Output: [3, 2, 1]

// Example 2
$root2 = null;
print_r(postorderTraversal($root2)); // Output: []

// Example 3
$root3 = new TreeNode(1);
print_r(postorderTraversal($root3)); // Output: [1]
?>





  
  
  설명:



TreeNode 클래스: TreeNode 클래스는 해당 값, 왼쪽 자식 및 오른쪽 자식을 포함하여 이진 트리의 노드를 정의합니다.

postorderTraversal 함수:


빈 결과 배열과 스택을 초기화합니다.
스택이 비어 있지 않거나 현재 노드가 null이 아닌 한 계속되는 while 루프를 사용합니다.
현재 노드가 null이 아니면 스택에 푸시하고 왼쪽 자식으로 이동합니다.
현재 노드가 null이면 스택의 최상위 노드를 확인합니다. 아직 방문하지 않은 오른쪽 자식이 있으면 오른쪽 자식으로 이동합니다. 그렇지 않으면 노드의 값을 결과 배열에 추가하고 스택에서 팝합니다.







이 반복 접근 방식은 시스템 재귀를 사용하지 않고 재귀적 후순 순회를 시뮬레이션하여 메모리 효율성을 높입니다.

연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 . 이진 트리 후위 순회의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!