Tree Traversal

树的遍历是大部分树题型的基础。

常用的遍历树的方法有BFS和DFS，

了解BFS的实现请戳DFS vs BFS

这里会详细介绍3种DFS遍历树的方法：
pre-order, in-order和 post-order。

它们之间的区别就在于父节点的访问顺序，

pre-order先访问父节点再访问左子树，最后到右子树。
图中pre-order: F, B, A, D, C, E, G, I, H
pre-order排列的第一个元素就是树的root

in-order先访问左子树，再访问父节点，最后到右子树。
图中in-order: A, B, C, D, E, F, G, H, I
in-order排列的左子树永远在parent左边，而右子树永远在parent右边

post-order先访问左子树，再访问右子树，最后才访问父节点。
图中post-order: A, C, E, D, B, H, I, G, F
post-order的最后一个元素就是树的root

任何时候只要知道树的三种排列中的两种，就能还原出一棵unique的树。

Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

input:

TreeNode root

output:

//print nodes

pre-order traversal:

public void preorder(TreeNode root) {
    if(root == null) return;
    System.out.print(root.val + “  “); //先访问根节点
    preorder(root.left);  //再访问左子树
    preorder(root.right);  //最后访问右子树
}

in-order traversal:

public void inorder(TreeNode root) {
    if(root == null) return;
    inorder(root.left);  //先访问左子树   
    System.out.print(root.val + “  “); //再访问根节点
    inorder(root.right);  //最后访问右子树
}

post-order traversal:

public void preorder(TreeNode root) {
    if(root == null) return;
    postorder(root.left);  //先访问左子树
    postorder(root.right);  //再访问右子树
    System.out.print(root.val + “  “); //最后访问根节点
}

相关真题：
Recover binary search tree given the in-order array
Tree serialization
Find kith smallest element in binary search tree
Maximum path sum of tree