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

岱永久会员 2024年12月26日下午8:42

前中后三种二叉树遍历的递归与非递归代码

先序遍历（中左右

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        preorder(root, ans);
        return ans;
    }

    private void preorder(TreeNode root, List<Integer> ans){
        if(root == null)return ;
        ans.add(root.val);
        preorder(root.left,ans);
        preorder(root.right,ans);
    }
}

class Solution{
    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();
            list.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }

        }
        return list;
    }
}

后序遍历（左右中

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        preorder(root, ans);
        return ans;
    }

    private void preorder(TreeNode root, List<Integer> ans){
        if(root == null)return ;
        preorder(root.left,ans);
        preorder(root.right,ans);
        ans.add(root.val);
    }
}

迭代

前序遍历的过程是中左右。
将其转化成中右左。也就是压栈的过程中优先压入左子树，在压入右子树。

然后将这个结果返回来，这里是利用栈的先进后出倒序打印。

//左右中 反过来就是中右左
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null)return ans;

        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);
        while(!s1.isEmpty()){
            TreeNode node = s1.pop();
            s2.push(node);
            //List.add(node.val);
            if(node.left!=null) s1.add(node.left);
            if(node.right!=null) s1.add(node.right);
        }
        while(!s2.isEmpty()){
            ans.add(s2.pop().val);
        }
        return ans;

    }


}

中序遍历（左中右）

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        preorder(root, ans);
        return ans;
    }
    private void preorder(TreeNode root, List<Integer> ans){
        if(root == null)return ;
        preorder(root.left,ans);
        ans.add(root.val);
        preorder(root.right,ans);
    }


}

class Solution{
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while( !stack.isEmpty() || cur != null){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node  = stack.pop();
            list.add(node.val);
            if(node.right!=null) cur = node.right;
        }
        return list;
    }

}

层序遍历

class Solution {
    public int[] decorateRecord(TreeNode root) {
        if(root == null ) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        ArrayList<Integer> ans = new ArrayList<>();
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            ans.add(node.val);
            if(node.left!=null)queue.add(node.left);
            if(node.right!=null)queue.add(node.right);
        }
        //ArrayList变为数组
        int[] res = new int[ans.size()];
        for(int i = 0;i<ans.size();i++){
            res[i] = ans.get(i);
        }
        return res;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年12月17日上午12:02

vector<int> preorder(TreeNode* root){ //前
    stack<TreeNode*> st;
    vector<int> result;
    if(root == NULL) return result;
    st.push(root);
    while(!st.empty()){
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val);
         if(node->right) st.push(node->right);
        if(node->left) st.push(node->left);
    }
    return result;
}

vector<int> inorder(TreeNode* root){ //中
    stack<TreeNode*> st;
    vector<int> result;
    TreeNode* cur = root;
    while(cur || !st.empty()){
        if(cur){
            st.push(cur);
            cur = cur->left;
        }
        else{
            cur = st.top();
            st.pop();
            result.push_back(cur->val);
            cur = cur->right;
        }
    }
    return result;
}

vector<int> postorder(TreeNode* root){ //后
    stack<TreeNode*> st;
    vector<int> result;
    if(root == NULL) return result;
    st.push(root);
    while(!st.empty()){
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val);
        if(node->left) st.push(node->left);
        if(node->right) st.push(node->right);
    }
    reverse(result.begin(), result.end());
    return result;
}

0 赞同 0 条回复

🌟 普通 2024年12月14日下午6:00

“`cpp
//解
#include
#include
#include
#include
#include
using std::vector;
using std::cout;
using std::endl;

// 二叉树节点结构体定义
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector preorderTraversal(TreeNode *root){

vector<int> result;
std::stack<TreeNode*> node;
if(root!=nullptr) node.push(root);
while(!node.empty()){
    TreeNode* cur=node.top();
    node.pop();
    if(cur->right) node.push(cur->right);
    if(cur->left) node.push(cur->left);

    result.push_back(cur->val);
}
return result;

}

vector inorderTraversal(TreeNode *root){

vector<int> result;
std::stack<TreeNode*> node;

while(!node.empty()||root!=nullptr){

    while (root!=nullptr)
    {
        node.push(root);
        root=root->left;
    }

    TreeNode* cur=node.top();
    node.pop();
    result.push_back(cur->val);
    root=cur->right;

}
return result;

}

vector postorderTraversal(TreeNode root){
vector result;
std::stack<TreeNode> node;

while(!node.empty()||root!=nullptr){
    while (root!=nullptr)
    {
        node.push(root);
        root=root->right;
    }
    TreeNode* cur=node.top();
    node.pop();
    result.push_back(cur->val);
    root=cur->left;
}
return result;

}

void printf_vec(vector vec){
for(auto &it:vec){
cout<<it<<” “;
}
cout<<“\n”;
}

void destory_tree(TreeNoderoot){
if(rootnullptr) return;
if(root->left) destory_tree(root->left);
if(root->right) destory_tree(root->right);
delete root;
}
int main() {
TreeNode root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);

cout << "前序遍历结果: ";//1 2 4 5 3 6 7
printf_vec(preorderTraversal(root));


cout << "中序遍历结果: ";// 4 2 5 1 6 3 7
printf_vec(inorderTraversal(root));


cout << "后序遍历结果: ";// 7 3 6 1 5 2 4
printf_vec(postorderTraversal(root));
destory_tree(root);
return 0;

}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月4日下午10:05

题解
使用队列先进先出的性质，先遍历到的会被记录下来，再复杂操作中可以把数据放到队列里面暂存

class Solution {
    public int[] decorateRecord(TreeNode root) {
        if (root == null) {
            // 【错误点1】：int[]的new的方式
            return new int[0];
        }
        // 定义队列去按照访问顺序放入元素
        // 【错误点2】:泛型元素的声明
        Queue<TreeNode> q = new LinkedList();
        // 定义链表存放值（因为个数不确定，不能建立数组了）
        List<Integer> resultList = new ArrayList();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode tmpt = q.poll();
            // 值放入list中
            resultList.add(tmpt.val);
            // 左右节点放入队列中
            if (tmpt.left != null) {
                q.offer(tmpt.left);
            }
            if (tmpt.right != null) {
                q.offer(tmpt.right);
            }
        }
        // 链表的数据放到数组里面
        int[] reslut = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            reslut[i] = resultList.get(i);
        }
        return reslut;
    }
}

错误点1：数组的初始化。int[]=new int[数组长度]
错误点2：泛型要放入正确的类型，这里就要放入Node类型，而不是Integer类型

0 赞同 0 条回复

Tom Yuan 普通 2024年12月4日上午7:37

# 前序
def preorder_traversal(root):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        if node:
            result.append(node.value)  # 访问当前节点
            stack.append(node.right)  # 先压入右子节点
            stack.append(node.left)   # 再压入左子节点
    return result

# 中序
def inorder_traversal(root):
    stack, result = [], []
    current = root
    while stack or current:
        while current:
            stack.append(current)  # 将左节点压入栈
            current = current.left
        current = stack.pop()
        result.append(current.value)  # 访问当前节点
        current = current.right       # 转向右子节点
    return result

# 后序
# 和前序几乎相同，但是压入左右的顺序换了一下，最终结果从末尾开始输出
def inorder_traversal(root):
    stack, result = [], []
    current = root
    while stack or current:
        while current:
            stack.append(current)  # 将左节点压入栈
            current = current.left
        current = stack.pop()
        result.append(current.value)  # 访问当前节点
        current = current.right       # 转向右子节点
    return result

0 赞同 0 条回复

无言永久会员 2024年12月3日下午5:26

//前序
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> stk;
    TreeNode* node = root;
    while(!stk.empty() || node) {
        while(node) {
            stk.push(node);
            ans.push_back(node->val);
            node = node->left;
        }
        node = stk.top();
        stk.pop();
        node = node->right;
    }
    return ans;
}
//中序
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> stk;
    TreeNode* node = root;
    while(!stk.empty() || node) {
        while(node) {
            stk.push(node);
            node = node->left;
        }
        node = stk.top();
        stk.pop();
        ans.push_back(node->val);
        node = node->right;
    }
    return ans;
}
//后序
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> stk;
    TreeNode* node = root;
    TreeNode* prev = nullptr;
    while(!stk.empty() || node) {
        while(node) {
            stk.push(node);
            node = node->left;
        }
        node = stk.top();
        stk.pop();
        if(node->right == nullptr || node->right == prev){
            ans.push_back(node->val);
            prev = node;
            node = nullptr;
        } else {
            stk.push(node);
            node = node->right;
        }
    }
    return ans;  
}

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午6:52

/**
先序遍历
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        Deque<TreeNode> st = new ArrayDeque<>();
        List<Integer> res = new ArrayList<>();

        st.add(root);
        while (!st.isEmpty()){
            TreeNode cur = st.pollLast();
            res.add(cur.val);
            if (cur.right != null){
                st.add(cur.right);
            }
            if (cur.left != null){
                st.add(cur.left);
            }
        }
        return res;
    }
}

/**
中序遍历模版
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {

        Deque<TreeNode> st = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        TreeNode p = root;
        while (!st.isEmpty() || p != null){
            while (p != null){
                st.add(p);
                p = p.left;
            }
            TreeNode cur = st.pollLast();
            ans.add(cur.val);
            p = cur.right;
        }
        return ans;

    }
}

/**
 后序遍历
 由先序改造而来,MLR->MRL->LRM
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {

        if (root == null){
            return new ArrayList<>();
        }
        Deque<TreeNode> st = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        st.add(root);
        while (!st.isEmpty()){
            TreeNode cur = st.pollLast();
            ans.add(0, cur.val);
            if (cur.left != null){
                st.add(cur.left);
            }
            if (cur.right != null){
                st.add(cur.right);
            }
        }
        return ans;


    }
}

0 赞同 0 条回复

Renasc 普通 2024年11月30日下午2:37

// 1. 先序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        List<Integer> res = new ArrayList<>();

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);

            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return res;
    }
}

// 2. 中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            TreeNode node = stack.pop();
            res.add(node.val);
            root = node.right;
        }
        return res;
    }
}

// 3. 后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        List<Integer> res = new ArrayList<>();

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);

            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        Collections.reverse(res);
        return res;
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年11月30日下午2:34

前序遍历：
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        TreeNode tmp;
        stack.push(root);
        while(!stack.empty()){
            tmp=stack.pop();
            if(tmp!=null){
                result.add(tmp.val);
            }else{
                continue;
            }
            stack.push(tmp.right);
            stack.push(tmp.left);
        }
        return result;
    }
}
后序遍历：
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        TreeNode tmp;
        stack.push(root);
        while(!stack.empty()){
            tmp=stack.pop();
            if(tmp!=null){
                result.add(tmp.val);
            }else{
                continue;
            }
            stack.push(tmp.left);
            stack.push(tmp.right);
        }
        Collections.reverse(result);
        return result;
    }
}
中序遍历：
class Solution {
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> res=new ArrayList<>();
        if(root==null) return res;
        Stack<TreeNode> stk=new Stack<>();
        TreeNode cur=root;
        while(!stk.empty()||cur!=null){
            if(cur!=null){
                stk.push(cur);
                cur=cur.left;
            }else{
                TreeNode tmp=stk.pop();
                cur=tmp;
                res.add(tmp.val);
                cur=cur.right;
            }
        }
        return res;

    }
}

0 赞同 0 条回复

lQl 永久会员 2024年11月29日下午6:43

public class BinaryTreeTraversal{
    //先序遍历
    public List<Integer> preorder(TreeNode root){
        List<Integer> result = new ArrayList<>();
        if(root==null)return result;

        Stack<TreeNode> s = new Stack<>();
        stack.push(root);

        while(!s.isEmpty()){
            TreeNode node = s.pop();
            result.add(node.val);
            if(node.right !=null)stack.push(node.right);
            if(node.left!=null)stack.push(node.left);
        }
        return result
    }
    //中序遍历
    public List<Integer> inorder(TreeNode root){
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        Tree current = root;

        while(current!=null||!s.isEmpty()){
            while(current!=null){
                s.push(current);
                current = current.left;
            }
            current = s.pop();
            result.add(current);
            current = current.right;
        }
        return result;
    }
    //后序遍历
    public List<Integer> postorder(TreeNode root){
        LinkedList<Integer> result = new LinkedList<>();
        Stack<TreeNode> s = new Stack<>();
        if(root == null) return result;
        s.push(root);

        while(!s.isEmpty()){
            TreeNode node = s.pop();
            result.addFirst(node.val);
            if(node.left!=null)s.push(node.left);
            if(node.right!=null)s.push(node.right);
        }
        return result;
    }   
}

0 赞同 0 条回复

迢迢星野普通 2024年11月29日下午2:49

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
// 访问路径和要读的路径重合
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
// 访问路径和要读的路径不重合
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               // 一路向左
               stack.push(cur);
               cur = cur.left;
           }else{
               // 出栈变右
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

0 赞同 0 条回复

月下足迹普通 2024年11月29日上午11:43

//前序
public class BinaryTreeTraversal {
public List preorderTraversal(TreeNode root) {
List result = new ArrayList<>();
if (root null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val); // 访问当前节点

        if (node.right != null) stack.push(node.right); // 先右子节点入栈
        if (node.left != null) stack.push(node.left);   // 后左子节点入栈
    }

    return result;
}

}

//中序
public class BinaryTreeTraversal {
public List inorderTraversal(TreeNode root) {
List result = new ArrayList<>();
Stack stack = new Stack<>();
TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current); // 把当前节点压栈
            current = current.left; // 移动到左子节点
        }

        current = stack.pop(); // 弹出栈顶节点
        result.add(current.val); // 访问当前节点
        current = current.right; // 转向右子节点
    }

    return result;
}

}

//后序
public class BinaryTreeTraversal {
public List postorderTraversal(TreeNode root) {
List result = new ArrayList<>();
if (root null) return result;

    Stack<TreeNode> stack = new Stack<>();
    Stack<TreeNode> output = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        output.push(node); // 当前节点压入输出栈

        if (node.left != null) stack.push(node.left); // 左子节点入栈
        if (node.right != null) stack.push(node.right); // 右子节点入栈
    }

    while (!output.isEmpty()) {
        result.add(output.pop().val); // 从输出栈依次取出
    }

    return result;
}

}

0 赞同 0 条回复

jaron 普通 2024年11月29日上午10:23

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
// 访问路径和要读的路径重合
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
// 访问路径和要读的路径不重合
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               // 一路向左
               stack.push(cur);
               cur = cur.left;
           }else{
               // 出栈变右
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

0 赞同 0 条回复

苯庸普通 2024年11月29日上午10:18

class Solution {
Stack st = new Stack();
public List postorderTraversal(TreeNode root) {
TreeNode visited = null;
List res = new ArrayList();
pushLeft(root);
while(!st.isEmpty()){
TreeNode cur = st.peek();
if((cur.left null || cur.left visited) && cur.right != visited){
// 中序
pushLeft(cur.right);
}
if(cur.right null || cur.right visited){
visited = st.pop();
//后序

            res.add(visited.val);
        }
    }
    return res;
}

void pushLeft(TreeNode cur){
    while(cur != null){
        // 前序
        st.push(cur);
        cur = cur.left;
    }
}

}

0 赞同 0 条回复

youngsir 普通 2024年11月29日上午10:12

/**
前序遍历 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.push(root->right);
                res.push_back(root->val);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
        }
        return res;

    }
};
/**
中序遍历
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        while(root != nullptr || !stk.empty()){
            while(root!=nullptr){
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;

    }
};
/**
后序遍历
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        while(root!=nullptr || !stk.empty()){
            while(root!=nullptr){
                stk.push(root->left);
                res.push_back(root->val);
                root = root->right;
            }
            root = stk.top();
            stk.pop();
        }
        reverse(res.begin(), res.end()); 
        return res;
    }
};

0 赞同 0 条回复

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

共以下 15 个回答

前中后三种二叉树遍历的递归与非递归代码

# 回答此问题取消回复

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

共以下 15 个回答

前中后三种二叉树遍历的递归与非递归代码

# 回答此问题 取消回复

# 回答此问题取消回复