【二叉树专题】额外要求：前中后三种二叉树遍历的非递归代码-跟着帅地玩副业，开拓第二曲线PlayOffer

Miracle· 普通 2023年9月4日下午10:49

前序遍历:
// 递归遍历
void preorder(TreeNode* root, vector &res) {
if (root nullptr) return;
res.emplace_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    preorder(root, res);
    return res;
}

中序遍历:
// 递归遍历
void inorder(TreeNode* root, vector &res){
if (root nullptr) return;
inorder(root->left, res);
res.emplace_back(root->val);
inorder(root->right, res);
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    inorder(root, res);
    return res;
}

后序遍历:
// 递归
void postorder(TreeNode root, vector &res){
if (root nullptr) return;
postorder(root->left, res);
postorder(root->right, res);
res.emplace_back(root->val);
}
vector postorderTraversal(TreeNode root) {
vector res;
postorder(root, res);
return res;
}
层序遍历:
// 迭代,采用队列来存节点
vector<vector> levelOrder(TreeNode* root) {
vector<vector> res; // 存放树的层序遍历数组
if (root nullptr) return res;
queue<TreeNode*> que; // 使用队列来辅助存储树节点
que.emplace(root);
while (!que.empty()) {
int size = que.size(); // 获得当前层数的节点个数
vector cur; // 表示当前层数的节点
for (int i = 1; i <= size; ++i) {
auto node = que.front();
que.pop();
cur.emplace_back(node->val);
if (node->left) que.emplace(node->left);
if (node->right) que.emplace(node->right);
}
res.emplace_back(cur); // 把当前层的节点数组加入到总的结果数组中
}
return res;
}

0 赞同 0 条回复

sincere 普通 2023年8月23日下午5:24

思路：借助辅助栈存储节点

// preorder
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        return list;
    }
}
// inorder
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        while (cur != null || !stack.empty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }
}
// postorder
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.left!=null){
                stack.push(node.left);
            }
            if (node.right!=null){
                stack.push(node.right);
            }
        }
        Collections.reverse(list);
        return list;
    }
}

0 赞同 0 条回复

Sheng 永久会员 2023年8月21日下午9:36

//前序遍历
    public List<Interger> preorderTraversal(TreeNode root) {
        if(root == null) return new LinkedList<Integer>();

        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new LinkedList<Integer>();

        TreeNode node = root;
        while(node != null || !stack.isEmpty()) {
            if(node != null) {
                stack.push(node);
                result.add(node.val);
                node = node.left;
            }
            else {
                node = stack.pop();
                node = node.right;
            }
        }
        return result;  
    }
//中序遍历
    public List<Interger> midorderTraversal(TreeNode root) {
        if(root == null) return new LinkedList<Integer>();

        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new LinkedList<Integer>();

        TreeNode node = root;
        while(node != null || !stack.isEmpty()) {
            if(node != null) {
                stack.push(node);
                node = node.left;
            }
            else {
                node = stack.pop();
                result.add(node.val);
                node = node.right;
            }
        }
        return result;  
    }
//后序遍历
//二叉树的后序遍历 是 中右左为顺序的前序遍历 的 倒序
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if(noot == null) return new LinkedList<Integer>();

        Stack<TreeNode> stack = new Stack<>();
        LinkedList<Integer> result = new LinkedList<>();//只有LinkedList有addFirst方法

        //仿照前序遍历写的
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            if(cur != null) {
                stack.push(cur);
                result.addFirst(cur.val);//实现倒序
                cur = cur.right;
            }
            else {
                TreeNode top = stack.pop();
                cur = top.left;
            }
        }

        return result;
    }
}

1 赞同 0 条回复

别扒拉我普通 2023年8月20日下午11:03

1、先序遍历

class Solution {
    public List<Integer> preOrderRecursively(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        res.add(root.val);
        preOrderRecursively(root.left);
        preOrderRecursively(root.right);
        return res;
    }

    public List<Integer> preOrderIteratively(TreeNode tree){
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        TreeNode root = tree;
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            if(root != null){
                res.add(root.val);
                stack.push(root);
                root = root.left;
            }else{
                root = stack.pop().right;
            }
        }
        return res;
    }
}

2、中序遍历

    public List<Integer> inOrderRecursively(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        preOrderRecursively(root.left);
        res.add(root.val);
        preOrderRecursively(root.right);
        return res;
    }

    public List<Integer> inOrderIteratively(TreeNode tree){
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        TreeNode root = tree;
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            if(root != null){
                stack.push(root);
                root = root.left;
            }else{
                res.add(root.peek());
                root = stack.pop().right;
            }
        }
        return res;
    }
}

3、后序遍历

class Solution {
    public List<Integer> postOrderRecursively(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        preOrderRecursively(root.left);
        preOrderRecursively(root.right);
        res.add(root.val);
        return res;
    }

    public List<Integer> postOrderIteratively(TreeNode tree){
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        TreeNode root = tree;
        TreeNode prevVisted = null;
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            if(root != null){
                stack.push(root);
                root = root.left;
            }else{
                root = stack.peek().right;
                if(root != null && root != prevVisted){
                    stack.push(root);
                    root = root.left;
                }else{
                    prevVisted = stack.pop();
                    res.add(prevVisted.val);
                    root = null;
                }
            }
        }
        return res;
    }
}

0 赞同 0 条回复

c 普通 2023年8月20日下午9:40

//先序
public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
            list.add(node.val);
        }
        return list;
    }
//中序
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null){
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur=root;
        while(!stack.isEmpty() || cur!=null){
            while(cur!=null){
                stack.add(cur);
                cur=cur.left;
            }
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.right!=null){
                cur=node.right;
            }
        }
        return res;
    }
}
//后续
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode node=null;
        while(!stack.isEmpty() || cur!=null){
            while(cur!=null){
                stack.add(cur);
                cur=cur.left;
            }
            cur = stack.pop();
            if(cur.right == null || cur.right==node){
                list.add(cur.val);
                node=cur;
                cur=null;
            }else{
                stack.push(cur);
                cur = cur.right;
            }
        }

        return list;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年8月20日下午6:44

前序遍历

//递归版本
class Solution {
    public:
    vector<int> ans;
    void dfs(TreeNode* root,vector<int>&ans)
    {
        if(!root) return;
        ans.push_back(root->val);
        dfs(root->left,ans);
        dfs(root->right,ans);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return {};
        dfs(root,ans);
        return ans;
    }
};
//非递归版本
 // 通过栈来模拟递归，时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int>ans;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty())
        {
            TreeNode* node = stk.top();
            stk.pop();
            ans.push_back(node->val);
            if(node->right)
                stk.push(node->right);
            if(node->left)
                stk.push(node->left);
        }
        return ans;
    }
};

中序遍历

 // 递归版本，时间复杂度O(n)，空间O(n)
#include <vector>
class Solution {
  public:
    vector<int> ans;
    void dfs(TreeNode* root, vector<int>& ans) {
        if (!root) return;
        dfs(root->left,ans);
        ans.push_back(root->val);
        dfs(root->right,ans);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) return {};
        dfs(root, ans);
        return ans;
    }
};
 // 非递归版本，时间复杂度O(n),空间复杂度O(n)
class Solution {
public:

    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> ans;
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        while(cur || !stk.empty())
        {
            while(cur)
            {
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top();
            stk.pop();
            ans.push_back(cur->val);
            cur = cur->right;
        }
        return ans;
    }
};

后续遍历

 // 递归版本，时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector ans;
    void dfs(TreeNode* root,vector& ans)
    {
        if(!root) return;
        dfs(root->left,ans);
        dfs(root->right,ans);
        ans.push_back(root->val);
    }
    vector postorderTraversal(TreeNode* root) {
        if(!root) return {};
        dfs(root,ans);
        return ans;
    }
};
 // 非递归版本，将前序的遍历换一下，再进行导致
 // 时间O(n),空间O(n)
#include 
#include 
class Solution {
public:

    vector postorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector ans;
        stack stk;
        stk.push(root);
        while(!stk.empty())
        {
            TreeNode* node = stk.top();
            stk.pop();
            ans.push_back(node->val);
            if(node->left)
                stk.push(node->left);
            if(node->right)
                stk.push(node->right);
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月20日下午3:32

class Solution {
    // 前序遍历根左右
    public List preorderTraversal(TreeNode root) {
        List list = new ArrayList<>();
        Stack stack = new Stack<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                list.add(p.val);
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            if (p.right != null) {
                p = p.right;
            } else {
                p = null;
            }
        }
        return list;
    }
}

class Solution {
    //中序遍历左根右
    public List inorderTraversal(TreeNode root) {
        List list = new ArrayList<>();
        Stack stack = new Stack<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                 p = stack.pop();
                 list.add(p.val);
                 if (p.right != null) {
                     p = p.right;
                 } else {
                     p = null;
                 }
            }
        }
        return list;

    }
}

class Solution {
    //后序遍历左右根
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root, q = null;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                if (p.right == null || p.right == q) {
                    list.add(p.val);
                    q = p;
                    p = null;
                } else {
                    stack.push(p);
                    p = p.right;
                }
            }
        }
        return list;
    }
}

0 赞同 0 条回复

【二叉树专题】额外要求：前中后三种二叉树遍历的非递归代码

共以下 7 个回答

# 回答此问题取消回复

【二叉树专题】额外要求：前中后三种二叉树遍历的非递归代码

共以下 7 个回答

# 回答此问题 取消回复

# 回答此问题取消回复