Binary Tree 遍历模板小结

Binary Tree的遍历可分为preorder, inorder, postorder和in-level order四种。前3种可用递归或非递归(基于stack，后进先出)，第4种通常用BFS，基于queue(先进先出)，也可以用DFS，基于stack。注意这里是Binary Tree，不需要是Binary Search Tree。

preorder遍历非递归模板：
遍历顺序为根、左、右
思路：
1. 如果根节点非空，将根节点加入到栈中。
2. 如果栈不空，弹出栈顶节点，将其值加加入到数组中。
2.1 如果该节点的右子树不为空，将右子节点加入栈中。
2.2 如果左子节点不为空，将左子节点加入栈中。
3. 重复第二步，直到栈空。
代码如下：

    vector<int> preorderTraversal(TreeNode * root) {
        vector<int> result;
        stack<TreeNode*> s;

        if (!root)
            return result;

        s.push(root);
        while(!s.empty()) {
            TreeNode* temp = s.top();
            if (temp) 
                result.push_back(temp->val);
            s.pop();
            if (temp) {
                s.push(temp->right);
                s.push(temp->left);
            }
        }  
        return result;
    }

in-order非递归模板：（非常重要!!!）
遍历顺序为左、根、右

思路
1. 从根节点开始，开始把左节点挨个压栈，直至最左端的叶节点。
2. 若stack不为0，对node=stack.top()，存入结果。
若node无右节点，则pop()，并看node在stack前一个位置(也就是新的stack.top()是不是node的父节点，并且node是它的右节点）,若是，则将其pop()。
若node有右节点，则将其压栈，并将其左节点挨个压栈，直至其左子树的最左端的叶节点。

举例如下：
第一个while循环沿着左节点压栈，s={6,5,3,2}, 2是栈顶。
第二个while循环
先将node=s.top()的存入结果(2)，然后看node是否有右节点，这里没有，所以pop()。
然后新的node=s.top()存入结果(3)，这里因为3有右节点4（这里3不能pop()，否则4返回就找不到3了），所以将节点4压栈，s={6,5,3,4}。
然后新的node=s.top()存入结果(4)，这里4没有右节点，所以4pop()，然后我们看到4是3的右节点，所以3pop()。然后后面的循环会处理5,6,…。

代码如下(参考自九章)：

    vector<int> inorderTraversal(TreeNode * root) {

        vector<int> result;
        stack<TreeNode *> s;
        if (!root) return result;

        while(root) {
            s.push(root);
            root=root->left;
        }

        while(!s.empty()) {
            TreeNode* node=s.top();
            result.push_back(node->val);

            if (!node->right) {
                s.pop();
                while(!s.empty() && (s.top()->right==node)) {
                    node=s.top();
                    s.pop();
                }
            } else {
                node = node->right;
                while(node) {
                    s.push(node);
                    node=node->left;
                }
            }
        }

        return result;
    }

post-order非递归模板
遍历顺序为左、右、根。这个是3个遍历里面最复杂的，下次写。

in-level order 非递归版
思路: 用queue。
一开始将root放入queue中，然后进入while(!queue.empty())，若queue不为空，则按queue中有多少元素(queue.size())，不断取queue.front()，将其值存入结果，再将其左右节点push进queue。周而往复，直到queue空。
代码如下：

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Level order a list of lists of integer
     */
    vector<vector<int>> levelOrder(TreeNode * root) {
        vector<vector<int> > result;
        if (!root) return result;

        queue<TreeNode *> q;
        q.push(root);

        while(!q.empty()) {
            vector<int> vec;
            int size=q.size();
            for (int i=0; i<size; ++i) {
                TreeNode* node=q.front();
                q.pop();   
                vec.push_back(node->val);
                if (node->left) 
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);

            }
            result.push_back(vec);
        } 
        return result; 
    }
};