二叉树遍历

深度优先遍历

对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次
深度优先遍历可以细分为：

• 前序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树
• 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树
• 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根

具体实现方式可以分为：

• 递归
• 迭代

  广度优先遍历

  又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右(或者从右往左)访问节点，访问完一层就进入下一层，直到没有节点可以访问为止

深度优先-递归实现前序、中序、后序遍历

public void preOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.print(node.val + " ");
    preOrder(node.left);
    preOrder(node.right);
}

public void inOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    inOrder(node.left);
    System.out.print(node.val + " ");
    inOrder(node.right);
}

public void postOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    postOrder(node.left);
    postOrder(node.right);
    System.out.print(node.val + " ");
}

深度优先-递归实现前序、中序、后序遍历（返回结果）

public ArrayList<Integer> preOrder(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    preOrder(root, result);
    return result;
}
public void preOrder(TreeNode node, ArrayList<Integer> result) {
    if (node == null) {
        return;
    }
    result.add(node.val);
    preOrder(node.left, result);
    preOrder(node.right, result);
}

public ArrayList<Integer> inOrder(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    inOrder(root, result);
    return result;
}
public void inOrder(TreeNode node, ArrayList<Integer> result) {
    if (node == null) {
        return;
    }
    preOrder(node.left, result);
    result.add(node.val);
    preOrder(node.right, result);
}

public ArrayList<Integer> postOrder(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    postOrder(root, result);
    return result;
}
public void postOrder(TreeNode node, ArrayList<Integer> result) {
    if (node == null) {
        return;
    }
    preOrder(node.left, result);
    preOrder(node.right, result);
    result.add(node.val);
}

深度优先-迭代实现遍历（返回结果）

迭代实现需要借助 Stack（栈），利用 Stack（栈）的 LIFO（后进先出）的特性辅助实现

public ArrayList<Integer> deepOrder(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    // 将 root 节点放入栈
    stack.push(root);
    while (!stack.isEmpty()) {
        // 弹出栈顶元素
        TreeNode node = stack.pop();
        // 入栈顺序：先放左节点，后放右节点
        // 出栈顺序：先出右节点，后出左节点
        if (node.left != null) {
            // 放入弹出的栈顶元素的左子节点
            stack.push(node.left);
        }
        if (node.right != null) {
            // 放入弹出的栈顶元素的右子节点
            stack.push(node.right);
        }
        // 记录弹出的栈顶元素的值
        result.add(node.val);
    }
    return result;
}

public ArrayList<Integer> deepOrder(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    // 将 root 节点放入栈
    stack.push(root);
    while (!stack.isEmpty()) {
        // 弹出栈顶元素
        TreeNode node = stack.pop();
        // 入栈顺序：先放右节点，后放左节点
        // 出栈顺序：先出左节点，后出右节点
        if (node.right != null) {
            // 放入弹出的栈顶元素的右子节点
            stack.push(node.right);
        }
        if (node.left != null) {
            // 放入弹出的栈顶元素的左子节点
            stack.push(node.left);
        }
        // 记录弹出的栈顶元素的值
        result.add(node.val);
    }
    return result;
}

深度优先-迭代实现前序、中序、后序遍历（返回结果）

假设有一棵树：

            1            
         /     \         
      2           3      
    /   \       /   \    
  4       5   6       7  
 / \                     
8   9

广度优先-层次遍历（返回结果）

public ArrayList<Integer> levelOrder(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    // 将 root 节点放入队列
    queue.offer(root);
    while (!queue.isEmpty()) {
        // 弹出队首元素
        TreeNode node = queue.poll();
        if (node.left != null) {
            // 放入弹出的队首元素的左子节点
            queue.offer(node.left);
        }
        if (node.right != null) {
            // 放入弹出的队首元素的右子节点
            queue.offer(node.right);
        }
        // 记录弹出的队首元素的值
        result.add(node.val);
    }
return result;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(){}
    TreeNode(int val) {this.val = val;}
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}