二叉树的遍历

二叉树的遍历

二叉树的前序遍历（非递归）

方法一

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode *> Tree;
        vector<int> ret;
        while (!Tree.empty() || root != nullptr) {
            while (root != nullptr) {
                ret.push_back(root->val);
                Tree.push(root);
                root = root->left;
            }
            root = Tree.top();
            Tree.pop();
            root = root->right;
        }

        return ret;
    }
};

方法二

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (root == NULL) return ret;
        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode* node = s.top();
            s.pop();
            ret.push_back(node->val); // 记录先序遍历结果
            if (node->right) s.push(node->right);
            if (node->left) s.push(node->left);
        }
        return ret;
    }
};

中序遍历（非递归）

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (root == NULL) return ret;

        stack<TreeNode*> s;
        TreeNode* node = root;
        // 没有压入元素或者有未弹出的元素
        while (node || !s.empty())  {
            // 压入左子树
            while (node) {
                s.push(node);
                node = node->left;
            }
            // 弹出栈顶元素
            node = s.top();
            s.pop();
            ret.push_back(node->val); // 记录中序遍历结果
            // 进入右子树
            node = node->right;
        }
        return ret;
    }
};

中序遍历——颜色标记法

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        this.val = x;
        this.left = null;
        this.right = null;
    }
}

class ColorNode {
    TreeNode node;
    String color;
    ColorNode(TreeNode node, String color) {
        this.node = node;
        this.color = color;
    }
}
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if(root == null) return res;

    Stack<ColorNode> stack = new Stack<>();

    ColorNode colorNode = new ColorNode(root, "white");
    stack.push(colorNode);

    while(!stack.empty()) {
        colorNode = stack.pop();

        if(colorNode.color.equals("white")) {
            //RNL
            if(colorNode.node.right != null) {
                stack.push(new ColorNode(colorNode.node.right, "white"));
            }
            stack.push(new ColorNode(colorNode.node, "gray"));
            if(colorNode.node.left != null) {
                stack.push(new ColorNode(colorNode.node.left, "white"));
            }
        } else {
            res.add(colorNode.node.val);
        }
    }
    return res;
}

后序遍历（非递归）

方法一

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;  
        if(root == NULL) return ret;            
        stack<TreeNode*> s;  
        s.push(root);  
        while(!s.empty()) {  
            TreeNode *n = s.top();
            s.pop();
            ret.push_back(n->val); // 记录后续遍历的过程值

            if(n->left)  s.push(n->left);  
            if(n->right) s.push(n->right);  
        }
        reverse(ret.begin(), ret.end()); // 将ret倒置获得后序遍历结果
        return ret;
    }
};

方法二

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root == nullptr) return result;
        stack<TreeNode*> s;
        TreeNode *p = root, *r = nullptr;
        while(p || !s.empty()){
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top();
            if (p->right && p->right != r) { //考虑栈顶结点的右子树结点。存在且没被访问过，将右子树结点压入栈中
                p = p->right;
            } else {
                s.pop();
                result.push_back(p->val);
                r = p;
                p = nullptr;
                //p置空作用在于当原栈顶结点被访问并弹出后，下一层while是将当前栈顶结点的左子树入栈，当前栈顶结点的左子树已经被遍历过，     
            //因此会造成死循环，所以将p置空，直接考虑当前栈顶结点的右子树
            }
        }
        return result;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root == nullptr) return result;
        stack<TreeNode*> s;
        TreeNode *p = root, *r = nullptr;
        while(p || !s.empty()){
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top();
            if (p->right && p->right != r) {
                p = p->right;
            } else {
                s.pop();
                result.push_back(p->val);
                r = p;
                p = nullptr;
            }
        }
        return result;
    }
};

层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > ret;
        if (!root) return ret;

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int count = q.size();
            ret.push_back(vector<int>() );
            for (int i = 1; i <= count; ++i) { // 遍历当前层所有结点，并将其孩子结点入队
                TreeNode* node = q.front();
                q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return ret;
    }
};