二叉树的遍历.md

二叉树的遍历

二叉树有深度优先和广度优先两种遍历方式

其中深度优先遍历（dfs）又分为前序、中序、后序三种遍历方式

可以用递归和非递归方式实现

• 深度优先搜索
  • 前序遍历
  • 中序遍历
  • 后序遍历
• 宽度优先搜索

深度优先搜索模板

搜索模板

public class Solution {
    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // do something with root
        traverse(root.left);
        // do something with root
        traverse(root.right);
        // do something with root
    }
}

分治模板

public class Solution {
    public ResultType traversal(TreeNode root) {
        // null or leaf
        if (root == null) {
            // do something and return;
        }
        
        // Divide
        ResultType left = traversal(root.left);
        ResultType right = traversal(root.right);
        
        // Conquer
        ResultType result = Merge from left and right.
        return result;
    }
}