树的遍历（一）

树的递归遍历框架

二叉树遍历框架，典型的非线性递归遍历结构：

/*
      基本的二叉树结点
*/
class TreeNode{
      int val;
      TreeNode left, right;
}

void traverse(TreeNode root){
      traverse(root.left);
      traverse(root.right);
}

二叉树框架可以扩展为N叉树的遍历框架：

/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);
}

二叉树的遍历套用上面的框架：

void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

同理，N叉树遍历的递归方法如下:

void traverse(TreeNode root) {
    // 前序遍历
    for (TreeNode child : root.children){
          traverse(child);
    // 后序遍历
}

参考资料：labuladong的算法小抄

树的遍历递归框架如上，下面重点记录非递归遍历树的方法。

二叉树

前序遍历

实现二叉树的非递归前序遍历，我们可以利用栈这一数据结构，保证栈顶节点就是我们当前的遍历节点。

node = root
如果 node != null || !stack.isEmpty()
　　1）如果node != null
　　　　a. 将值add到res中
　　　　b. 将node推入栈中
　　　　c. node等于node.left，遍历左子树
　　2）弹出栈顶，node = node.right开始遍历右子树
返回结果

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()){
            while (node != null ){
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }

中序遍历

也是利用栈来实现二叉树的非递归中序遍历。代码基本相同，唯一不同的是node值在入栈后，再在出栈时add到res中。

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()){
            while(node != null){
                stack.push(node);
                node = node.left;
            }    
            node = stack.pop();
            res.add(node.val);   // 出栈add
            node = node.right;
        }
        return res;
    }

后序遍历

同样也是利用栈来完成，该解法的核心是同一个节点进两次栈，第一次出栈是进入该节点的右子树，第二次出栈将值add到res中。

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (true){
            while (root != null){  // 先将root的左子树都压入栈中
                stack.push(root);
                stack.push(root);
                root = root.left;
            }
            if (stack.isEmpty())
                break;
            root = stack.pop();
            if (!stack.isEmpty() && root == stack.peek())
                root = root.right;  // 第一次出栈
            else{
                res.add(root.val);  // 第二次出栈
                root = null;
            }
        }
        return res;
    }

N叉树

前序遍历

实现N叉树的非递归前序遍历，我们同样可以利用栈这一数据，需要保证栈顶的节点就是我们当前的遍历节点。

将根节点入栈
如果栈不为空，弹出栈顶结点
　　1）将值add到list中
　　2）将所有的子节点逆序推入栈中
栈为空，返回前序遍历的结果list

public List<Integer> preorder(Node root){
        Stack<Node> stack = new Stack<>();
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null)
            return res;
        stack.push(root);

        while(!stack.isEmpty()){
            Node node = stack.pop();
            res.add(node.val);
            for (int i = node.children.size() - 1; i>=0; i--)
                stack.add(node.children.get(i));     // 孩子节点倒着进栈
        }
        return res;
    }

后序遍历

使用两个栈，第一个栈将节点从上到下，从左到右压入，第二个栈存储后序遍历结果的倒叙，出栈即为后序遍历。

根节点进stack1
如果stack1不为空，栈顶节点出栈
　　1）压入stack2
　　2）孩子节点依次压入stack1
stack2中的节点依次出栈，将值add到res中，返回res

public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null){
            return list;
        }
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack1.push(root);
        while(!stack1.isEmpty()){
            Node node = stack1.pop();
            stack2.push(node);
            if (node.children != null){
                for (Node child : node.children){
                    stack1.push(child);
                }
            }
        }
        while (!stack2.isEmpty()){
            list.add(stack2.pop().val);
        }
        return list;
    }

层序遍历

层次遍历利用队列，需要保证当前队列是当前层次的节点，因此引入size控制list的大小。

root进入队列
如果队列不为空
　　1）记录当前层次的大小size
　　2）依次弹出size个节点，每个节点将值add到list中后，其子节点入队列
　　3）将某一层次的节点值list add到res中
返回结果

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null)
            return lists;
        List<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        while (!nodes.isEmpty()){
            int size = nodes.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++){
                TreeNode node = nodes.remove(0);
                list.add(node.val);
                // 二叉树
                if (node.left != null)
                    nodes.add(node.left);
                if (node.right != null)
                    nodes.add(node.right);
                // N叉树
              //for (Node child : node.children)
              //    nodes.add(child);   
            }
            lists.add(list);
        }
        return lists;

总结

树的遍历无非两种方法：递归和非递归。递归框架化较简单，非递归一般都是采用栈来实现。在各种遍历中，后续遍历相对较难，二叉树采取节点重复进栈的方式，N叉树则是利用双栈，从上到下，从左到右进栈后，依次出栈再入另外一个栈，这个栈的出栈的结果即为后序遍历（或者是队列，最后翻转）。