원본 링크:

binary-tree-preorder-traversal

binary-tree-inorder-traversal

binary-tree-postorder-traversal

전체적인 사고방식

세 문제의 해결 사고방식은 통일될 수 있고 틀도 매우 비슷하여 9장이 제공한 것보다 더욱 아름답다.

두 갈래 트리를 왼쪽으로 나눈다(왼쪽으로 지나가는 모든 실제 왼쪽 + 뿌리 포함), 오른쪽(실제 오른쪽 포함) 두 노드

동일한 순서로 왼쪽 노드를 창고에 넣기

적당한 시기에 방향을 바꾸고(방향을 바꾸면'오른쪽'노드는 바로'왼쪽'노드가 된다), 방문 노드, 또는 창고 출입

예를 들어 {1,2,3},cur가 노드 1에 있을 때 1, 2는'좌'노드에 속하고 3은'우'노드에 속한다.DFS의 비귀속 실현은 본질적으로 입고와 출고와 접근, 세 가지 조작의 순서를 조율하는 것이다.상술한 통일로 인해 우리는 더 이상 입고순서에 관심을 가질 필요가 없고 출고와 방문(3점)에만 관심을 가져야 한다. 더욱 상세한 분석에 따라 이런 간소화가 가져오는 장점을 더욱 느낄 수 있을 것이다.
노드에 대한 액세스를 다음과 같이 정의합니다results.add(node.val);.

선서 & & 중서:

선서와 중서의 상황은 매우 비슷하다.

순서의 실제 순서: 뿌리 좌우

중 순서의 실제 순서: 왼쪽 루트 오른쪽

상술한 사고방식을 사용하면 선순과 중순의 반복 순서는'좌','우'로 통일할 수 있다.
우리에게 직관적인 느낌은 코드도 비교적 비슷할 것이다.실제 상황은 바로 이렇다. 선순과 중순의 차이는 단지 왼쪽 노드에 대한 접근에 있다.

선순적 실현

창고에 들어갈 필요가 없습니다. 매번 "좌"노드를 훑어볼 때마다 즉시 출력하면 됩니다.
주의해야 할 것은 가장 왼쪽 아래의 노드를 두루 훑어보았을 때 실제로 출력된 것은 더 이상 실제 루트 노드가 아니라 실제 왼쪽 노드이다.이것은 선순의 정의에 부합된다.

while (cur != null) {
    results.add(cur.val);
    stack.push(cur);
    cur = cur.left;
}

이후, 우리는 이미 모든'좌'노드를 방문했기 때문에, 지금은 이 쓸모없는 노드를 창고에서 꺼내서'우'노드로 돌리기만 하면 된다.그리하여'우'노드도'좌'노드가 되었고 후속 처리는 같다.

if (!stack.empty()) {
    cur = stack.pop();
    //  
    cur = cur.right;
}

전체 코드는 다음과 같습니다.

private List dfsPreOrder(TreeNode root) {
    ArrayList results = new ArrayList<>();
    Stack stack = new Stack<>();

    TreeNode cur = root;
    while (cur != null || !stack.empty()) {
        while (cur != null) {
            results.add(cur.val);
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        //  
        cur = cur.right;
    }

    return results;
}

중서의 실현

선순에 대한 분석을 바탕으로 “ ” 우리는 코드 한 줄을 조정하면 중순을 반복할 수 있다.

while (cur != null) {
    stack.push(cur);
    cur = cur.left;
}
cur = stack.pop();
results.add(cur.val); //  
//  
cur = cur.right;

주의해라, 우리는 창고를 나간 후에야 이 노드를 방문할 수 있다.먼저 실제 뿌리에 접근하고, 나중에 실제 왼쪽에 방문하고, 중서는 정반대이기 때문이다.마찬가지로 루트 + 왼쪽 트리 (선순) 또는 왼쪽 트리 + 루트 (중순) 를 방문한 후 오른쪽 노드로 방향을 바꾸어 오른쪽 노드를 새 왼쪽 노드라고 부른다.
전체 코드는 다음과 같습니다.

private List dfsInOrder(TreeNode root) {
    List results = new ArrayList<>();
    Stack stack = new Stack();
    TreeNode cur = root;
    while (cur != null || !stack.empty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        results.add(cur.val);
        cur = cur.right;
    }
    return results;
}

후순

뒤의 상황은 약간 다르지만 여전히 매우 간결하다.

뒷순서의 실제 순서: 좌우근

입고순서는 변하지 않습니다. 우리는 제3점의 변화만 고려할 수 있습니다 .창고를 나가는 대상은 반드시'좌'노드일 것이다. ('우'노드는 방향을 바꾼 후에'좌'노드라고 부르고 창고에 들어간다), 즉 실제 좌 또는 뿌리이다.실제 왼쪽은 좌우 나무가 모두null의 뿌리라고 할 수 있기 때문에 우리는 실제 뿌리만 분석할 수 있다.
실제 뿌리에 대해서는 선후로 왼쪽 나무, 오른쪽 나무를 방문한 후에야 뿌리에 접근할 수 있다.실제 오른쪽 노드, 왼쪽 노드, 루트 노드는 모두 "왼쪽"노드가 되어 창고에 들어갈 수 있기 때문에 우리는 창고를 나가기 전에 이 노드를 실제 루트 노드로 간주하고 오른쪽 트리가 접근했는지 확인하면 된다.만약 오른쪽 트리가 존재하지 않거나 오른쪽 트리가 접근했다면 루트 노드에 접근할 수 있고 창고를 나갈 수 있으며 방향을 바꿀 필요가 없습니다.만약 아직 방문하지 않았다면 방향을 바꾸어 오른쪽 노드를 왼쪽 노드로 만들고 먼저 방문한 후에 루트 노드를 방문하도록 하세요.
그래서 우리는 오른쪽 나무의 방문 상황을 기록하는 표지를 추가해야 한다.루트 노드를 방문하기 전에 반드시 오른쪽 트리에 바짝 붙어 접근해야 하기 때문에 우리는 표지 위치만 필요로 한다.
전체 코드는 다음과 같습니다.

private List dfsPostOrder(TreeNode root) {
    List results = new ArrayList<>();
    Stack stack = new Stack<>();
    
    TreeNode cur = root;
    TreeNode last = null;
    while(cur != null || !stack.empty()){
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.peek();
        if (cur.right == null || cur.right == last) {
            results.add(cur.val);
            stack.pop();
            //  
            //  “ ， ”
            last = cur;
            //  ， 
            cur = null;
        } else {
            cur = cur.right;
        }
    }
    
    return results;
}

총결산

생각이 간결하다 만세!템플릿 대법 만세!
인류의 폭정을 없애면 세계는 삼체에 속한다!
본문 링크: [문제 풀이] 두 갈래 나무 비귀속 역력자: 원숭이 007 출처:https://monkeysayhi.github.io본고는 지식 공유 서명 - 같은 방식으로 4.0 국제 허가 협의 발표를 공유하고 전재, 연역 또는 상업 목적으로 사용하는 것을 환영하지만 본고의 서명과 링크를 보류해야 합니다.