Java 二叉树遍历的常用方法

void traverse(Treenode root) {
    //终止条件
    if(root == null) return;
    // 前序遍历
    traverse(root.left);
    // 中序遍历
    traverse(root.right);
    // 后序遍历
}

void traverse(TreeNode root) {
    if(root == null) return;
    visit(root);
    traverse(root.left);
    traverse(root.right);
}

void traverse(TreeNode root) {
    if(root ==null) return;
    traverse(root.left);
    visit(root);
    traverse(root.right);
}

void traverse(TreeNode root) {
    if(root ==null) return;
    traverse(root.left);
    traverse(root.right)
}

 public void traverse(TreeNode root) {
    // 边界判断
    if (root == null) {
      return;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
       //节点非空时，证明父节点的左侧节点非空，直接入栈
      if (current != null) {
        //前序遍历 visit(current)
        stack.push(current);
        current = current.left;
      } else {
        //节点为空，证明左侧节点为空，出栈，更换游标节点方向
        current = stack.pop();
		//中续遍历 visit(current);
        current = current.right;
      }
    }
  }

//使用双栈来实现后序遍历
  public void postOrderTraverse(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    Stack<Integer> res = new Stack<>();
    TreeNode cur = root;
    while (cur!=null || !stack.isEmpty()) {
      if (cur!=null){
        stack.push(cur);
        res.push(cur.val);
        cur = cur.right; //修改处
      }else{
        cur = stack.pop();
        cur = cur.left;  // 修改处
      }
    }
    while (!res.isEmpty()){
      visit(res.pop());
    }
  }

int BFS(Node start,Node target){
    Queue<Node> q; //核心数据结构
    Set<Node> visited: //某些情况下可以通过byte数组来进行代替
    int step = 0; //记录扩散步数
    //起始节点入队列
    q.add(start);
    visited.offer(start);
    while(q not empty) {
        //必须要用sz来保存q.size()，然后扩散sz不能直接使用q.size()
        int sz = q.size();
        //将队列中的节点进行扩散
        for(int i =0 ; i < sz; i++) {
            Node cur = q.poll();
            // 目标节点判断
            if(cur is target) {
                return step;
            }
            // 邻接结点入队列
            for(Node n:cur.adjs) {
                //未访问节点入队列
                if(n is not int visited) {
                    visitd.add(n);
                    q.offer(n);
                }
            }
        }
        // 更新步数
        step++;
    }
}

void LevelOrder(TreeNode root){
    //初始化栈，并放入
    Queue<TreeNode> queue;
    queue.add(root);
    while( !queue.isEmpty()) {
        //出栈
        TreeNode cur = queue.poll();
        //访问节点
        visit(cur);
        //向下一层级扩散
        if(cur.left !=null) queue.add(cur.left);
        if(cur.right !=null) queue.add(cur.right);
    }
}