二叉树遍历(非递归写法)

先序遍历

/**
 * 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> path;
        if(root == nullptr) return path;
        stack<TreeNode *> _stack;
        _stack.push(root);
        while(!_stack.empty()) {
            TreeNode *node = _stack.top();
            path.push_back(node->val);
            _stack.pop();
            if(node->right != nullptr)
                _stack.push(node->right);
            if(node->left != nullptr)
                _stack.push(node->left);
        }
        return path;
    }
};

中序遍历

/**
 * 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> path;
        if(nullptr == root) return path;
        stack<TreeNode *> _stack;
        TreeNode *node = root;
        _stack.push(node);
        node = node->left;
        while(!_stack.empty() || node) {
            if(node) {
                _stack.push(node);
                node = node->left;
            } else {
                node = _stack.top();
                _stack.pop();
                path.push_back(node->val);
                node = node->right;
            }
        }
        return path;
    }
};

后序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <iostream>
#include <stack>
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> path;
        if(nullptr == root) return path;
        stack<TreeNode*> _stack;
        TreeNode *last_node = nullptr, *node = root;
        _stack.push(node);
        node = node->left;
        while(!_stack.empty() || node) {
            while(node) {
                _stack.push(node);
                node = node->left;
            }
            if(!_stack.empty()) {
                node = _stack.top();
                if(nullptr == node->right || node->right == last_node) {
                    // 右子树访问完毕
                    _stack.pop();
                    path.push_back(node->val);
                    last_node = node;
                    node = nullptr;
                } else {
                    node = node->right;
                }
            }
        }
        return path;
    }
};

层次遍历

// 所使用的数据结构主要是队列
void level_order(TreeNode* root) {
        TreeNode* ptr = root;
        queue<TreeNode *> node_queue;
        node_queue.push(root);
        TreeNode *temp = nullptr;
        while(node_queue.size() > 0) {
            temp = node_queue.front();
            node_queue.pop();
            if(temp->left) {
                node_queue.push(temp->left);
            }
            if(temp->right) {
                node_queue.push(temp->right);
            }
        }
    }

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * 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>> re;
        if(!root) return re;
        queue<TreeNode *> _queue;
        _queue.push(root);
        int num_child = 1; // 记录每一层孩子的个数
        while(!_queue.empty()) {
            vector<int> path;
            int _num_child = 0;
            for(int i = 0; i < num_child && !_queue.empty(); ++i) {
                // 出队
                TreeNode *node = _queue.front();
                _queue.pop();
                path.push_back(node->val);
                if(node->left) {
                    ++_num_child;
                    _queue.push(node->left);
                    
                }
                if(node->right) {
                    ++_num_child;
                    _queue.push(node->right);
                }
            }
            num_child = _num_child;
            if(!path.empty())
                re.push_back(path);
        }
        return re;
    }
};