二叉树的遍历(递归and非递归)

树的遍历

前序

递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
private:
    void preorder(TreeNode* root, vector<int>& res){
        if (root == NULL) return;
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }
};

非递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        vector<TreeNode*> s{root};
        
        while (!s.empty()){
            TreeNode* t = s.back(); s.pop_back();
            res.push_back(t->val);
            if (t->right) s.push_back(t->right);
            if (t->left) s.push_back(t->left);
        }

        return res;
    }

中序

递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        
        inorder(root, res);
        
        return res;
    }
private:
    void inorder(TreeNode* root, vector<int> & res){
        if(!root) return;
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
};

非递归

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> nodes;
        stack<TreeNode*> todo;
        while (root || !todo.empty()) {
            while (root) {
                todo.push(root);
                root = root -> left;
            }
            root = todo.top();
            todo.pop();
            nodes.push_back(root -> val);
            root = root -> right;
        }
        return nodes;
    }
};

后序

递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorder(root, res);
        
        return res;
    }
private:
    void postorder(TreeNode* root, vector<int>& res){
        if (!root) return;
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }
};

非递归

Using one stack.

后序要保证一个节点要在左孩子和右孩子之后才能访问，那么有下面三种情况：

1.它是叶子节点，没有左右孩子。可以直接访问。

2.它有左右孩子，但是左右孩子都已经被访问过，也可以直接访问该节点。

3.有左右孩子，且左右孩子没有访问过。此时要先入栈右孩子，再入栈左孩子。

精简一下的话，因为后序遍历是左右根，如果一个节点被访问，一定是：1）右孩子为空；2）右孩子是上一个访问的节点。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> nodes;
        stack<TreeNode*> todo;
        TreeNode* last = NULL;//记录前一个访问节点---保证右孩子被访问过
        while (root || !todo.empty()) {
            if (root) {//左子树入栈，直到为空；
                todo.push(root);
                root = root -> left;
            } else {//root为空，说明左子树为空，stack的栈顶元素pop，正好是一个子树的根节点
                TreeNode* node = todo.top();
                //如果子树根节点右子树不为空，而且右子树还没有被访问，将节点更新为子树根节点的右孩子，然后再次循环
                // 和递归处理方法差不多，将右孩子所代表的子树，当做一颗新树，继续访问
                if (node -> right && last != node -> right) {
                    root = node -> right;
                } else {//节点的右孩子为空，或者右孩子是上一个访问节点，开始访问这个子树‘根’节点
                    nodes.push_back(node -> val);
                    last = node;
                    todo.pop();
                }
            }
        }
        return nodes;
    }
};

Using two stacks.

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack1;//用来颠倒顺序的： pop(root); push(left); push(right);
        stack<TreeNode*> stack2;//存储真正的访问顺序 左；右；根；；；栈顶元素是左: push(root),push(right),push(left)
        // 最后访问stack2，得到left，right，root；
        TreeNode* cur = root;
        if (cur == nullptr) return {};
        
        stack1.push(root);
        
        while (!stack1.empty()){
            TreeNode* temp = stack1.top();
            stack1.pop();
            stack2.push(temp);//根
            if (temp->left) stack1.push(temp->left);
            if (temp->right) stack1.push(temp->right);
        }
        while (!stack2.empty()){// stack2中存储顺序根右左，输出顺序：左右根
            res.push_back(stack2.top()->val);
            stack2.pop();
        }
        
        return res;
    }

};

层序

分层输出

递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        levelorder(root, 1, res);
        
        return res;
    }
private:
    void levelorder(TreeNode* root, int level, vector<vector<int>>& res){
        if (root == nullptr) return;
        // a little trick: 当当前访问层大于res已有容量，创建新vector容器，装载本层的访问数据
        if (level > res.size()) res.push_back(vector<int>());
        // 注意创建新容器的条件， 而不是root != nullptr[会导致调用每个非空节点时，都会创建一个新容器，有多少节点创建多少容器wrong]
        res[level-1].push_back(root->val);//直接push_back,不用创建新容器
        levelorder(root->left, level+1, res);
        levelorder(root->right, level+1, res);
    }
};

非递归

分层输出

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) return {};
        vector<vector<int>> result;
        queue<TreeNode*> que;
        que.push(root);
        
        vector<int> layer;
        while (!que.empty()){
            int size = que.size();//记录当前层节点数目，否则出错--que.size()在动态变化
            while (size--){
                TreeNode* node = que.front();
                layer.push_back(node->val);
                que.pop();
                
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(layer);
            layer.clear();//清空容器
        }
        
        return result;
    }
};

整体输出

非递归

class Solution{
public:
    vector<int> levelOrder(TreeNode* root){
        if (root == nullptr) return {};
        vector<int> result;
        queue<TreeNode*> que;
        que.push(root);
        
        while (!que.empty()){
            TreeNode* temp = que.front();
            que.pop();
            result.push_back(temp->val);
            if (temp->left) que.push(temp->left);
            if (temp->right) que.push(temp->right);
        }

        return result;
    }
}

Solution

一般情况下，都可以用递归方法解决–树本身的定义就是递归定义。

• 终止条件
• 递进的过程
• 回归的过程

一般情况是 递进->终止条件->回归。