두 갈래 나무가 번갈아 다니다

1. 앞의 순서 반복:
사상: 먼저 하나의 Stack을 만들어서 노드를 저장합니다. 이때 Stack은 비어 있습니다. 먼저 루트 결점을 Stack에 넣고 앞의 순서를 반복하는 것은 뿌리와 왼쪽, 오른쪽을 결합하는 선진적인 특징입니다. 다시 창고에 들어가는 것은 오른쪽 노드입니다. 따라서 결점의 오른쪽 나무가 비어 있지 않으면 창고에 들어가고 왼쪽 나무가 창고에 들어가는 것을 판단합니다. 코드 예시:

 public List preorderTraversal(TreeNode root) {
         Stack stack = new Stack<>();
        List list = new LinkedList<>();
        if(root == null){
            return list;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }
        return list;
    }

2. 중서 두루 훑어보다
사상: Stack을 만들고 왼쪽 중 오른쪽을 눌러 체인 테이블에 추가합니다. 가능한 한 이 노드의 왼쪽 트리를 창고에 넣으십시오. 이때 창고 꼭대기의 요소는 가장 왼쪽의 요소입니다. 오른쪽 노드가 있으면 중순으로 훑어보십시오.

 public List inorderTraversal(TreeNode root) {
        List list = new LinkedList<>();
        Stack stack = new Stack<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right != null){
                cur = node.right;
            }
        }
        return list;
    }

세 번째, 뒤 순서가 두루 다니다

  public List postorderTraversal(TreeNode root) {
  LinkedList stack = new LinkedList<>();
    LinkedList output = new LinkedList<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pollLast();
      output.addFirst(node.val);
      if (node.left != null) {
        stack.add(node.left);
      }
      if (node.right != null) {
        stack.add(node.right);
      }
    }
    return output;
    }