大大普通 2023年12月21日上午10:53

c++前中后序遍历非递归解法
class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
      stacks;
      vectorans;
      if(!root)return ans;
      s.push(root);
      while(!s.empty()){
          TreeNode* top=s.top();
          s.pop();
          ans.push_back(top->val);
          if(top->right)s.push(top->right);
           if(top->left)s.push(top->left);           
      }
      return ans;
    }
};

 //中序遍历
class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
     vectorans;
     stacks;
     if(!root)return ans;
    
     while(root||!s.empty()){
        while(root){
            s.push(root);
            root=root->left;
        }

         TreeNode* ttop=s.top();
         s.pop();
         ans.push_back(ttop->val);
         if(ttop->right)root=ttop->right;
         else root=NULL;
     }
     return ans;
    }
};

0 赞同 1 条回复

大大普通 @ 大大 2023年12月22日上午9:35

后序 比中序多了个tmp 避免重复
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
     vector<int>ans;
     TreeNode* tmp=NULL;
     if(root==NULL)return ans;
     stack<TreeNode*>s;
     while(!s.empty()||root){
      while(root){
          s.push(root);
          root=root->left;
      }
      TreeNode* top=s.top();
      if(top->right&&top->right!=tmp)
      root=top->right;
      else {
          s.pop();
          ans.push_back(top->val);
          tmp=top;
          root=NULL;
      }
     }
     return ans;
    }
};

淡色花樱普通 2023年7月19日下午6:17

“`java
前序
public List preOrderNR(){
Stack stack = new ArraySrack<>();
List result = new ArrayList<>();
根节点入栈
stack.push(root);
while(!stack.isEmpty()) {
//出栈
Node cur = stack.pop();
result.add(cur.e);
//若右孩子不为空先将右孩子压入栈
if(cur.right!=null){
stack.push(cur.right);
}
if(cur.left!=null){
stack.push(cur.left);
}
}
return result;
}
中序
public List inOrderNR() {
Stack stack = new ArrayList<>();
while(!stack.isEmpty()||root!=null){
if(root!=null){
stack.push(root);
root=root.left;
}else{
Node node = stack.pop();
result.add(node.e);
root=node.right;
}
}
return result;
}
后序
public List postOrderNR() {
Stack Stack = new ArrayStack<>();
List result = new ArrayList<>();
stack.push(root);
while(!stack.isEmpty()){
Node cur = stack.pop();
result add(cur.e);
if(cur.left!=null){
stack.push(cur.left);
}
if(cur.right!=null){
stack.push(cur.right);
}
}
Collection.reverse(result);
return result;
}

0 赞同 0 条回复

WhyNot 普通 2023年7月19日下午4:26

“`C
前序遍历的非递归实现：
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};

void preorderTraversal(struct TreeNode* root) {
if (root NULL) {
return;
}

struct TreeNode* stack[1000];
int top = -1;
stack[++top] = root;

while (top >= 0) {
    struct TreeNode* node = stack[top--];
    printf("%d ", node->val);

    if (node->right != NULL) {
        stack[++top] = node->right;
    }

    if (node->left != NULL) {
        stack[++top] = node->left;
    }
}

}
中序遍历的非递归实现：
void inorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[1000];
int top = -1;
struct TreeNode* node = root;

while (node != NULL || top >= 0) {
    while (node != NULL) {
        stack[++top] = node;
        node = node->left;
    }

    node = stack[top--];
    printf("%d ", node->val);
    node = node->right;
}

}
后序遍历的非递归实现：
void postorderTraversal(struct TreeNode* root) {
if (root NULL) {
return;
}

struct TreeNode* stack[1000];
int top = -1;
struct TreeNode* node = root;
struct TreeNode* lastVisited = NULL;

while (node != NULL || top >= 0) {
    while (node != NULL) {
        stack[++top] = node;
        node = node->left;
    }

    struct TreeNode* peek = stack[top];

    if (peek->right != NULL && peek->right != lastVisited) {
        node = peek->right;
    } else {
        printf("%d ", peek->val);
        lastVisited = peek;
        --top;
    }
}

}

0 赞同 0 条回复

断舍离永久会员 2023年7月10日下午5:13

/*
     * 非递归前序遍历，使用数据结构栈
     * */
    public List<E> pre0rderNR(){
        Stack<Node> stack = new ArrayStack<>();
        List<E> result = new ArrayList<>();
        //根节点入栈
        stack.push(root);
        while (!stack.isEmpty()){
            //出栈
            Node cur = stack.pop();
            result.add(cur.e);
            //若右孩子不为空，先将右孩子压入栈
            if(cur.right != null){
                stack.push(cur.right);
            }
            //若左孩子不为空，再将左孩子压入栈
            if(cur.left != null){
                stack.push(cur.left);
            }
        }
        return result;
    }

    /*
     * 非递归中序遍历
     * 中序遍历与前、后遍历思路不同
     * 先一路向左遍历，按这个顺序将各左孩子节点加入栈
     * 直到叶子节点，进行出栈，将右孩子节点加入栈，不断重复这个过程，直到栈内为空结束
     * */
    public List<E> in0rderNR(){
        Stack<Node> stack = new ArrayStack<>();
        List<E> result = new ArrayList<>();
        while (!stack.isEmpty() || root != null){
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                Node node = stack.pop();
                result.add(node.e);
                root = node.right;
            }
        }
        return result;
    }

    /*
     * 非递归后序遍历
     * 颠倒前序遍历，加入栈的左右孩子顺序，最后颠倒整个集合，就可以完成后序遍历
     * */
    public List<E> postOrderNR(){
        Stack<Node> stack = new ArrayStack<>();
        List<E> result = new ArrayList<>();
        //根节点入栈
        stack.push(root);
        while (!stack.isEmpty()){
            //出栈
            Node cur = stack.pop();
            result.add(cur.e);
            //若左孩子不为空，再将左孩子压入栈
            if(cur.left != null){
                stack.push(cur.left);
            }
            //若右孩子不为空，先将右孩子压入栈
            if(cur.right != null){
                stack.push(cur.right);
            }
        }
        Collections.reverse(result);
        return result;
    }

0 赞同 0 条回复

BOZ 普通 2023年7月7日下午1:10

三种DFS以及BFS的非递归实现

struct BinaryTreeNode {
    int val;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
    BinaryTreeNode(int v): val(v), left(nullptr), right(nullptr) {}
};

class BinaryTree {
    BinaryTreeNode *root = nullptr;
public:
    BinaryTree() {}
    BinaryTree(const std::vector<int> &vals) {
        std::queue<BinaryTreeNode *> q;
        for(auto & val: vals) {
            if (root == nullptr) { // first node
                root = new BinaryTreeNode(val);
                q.push(root);
            } else {
                assert(!q.empty());
                auto node = q.front();
                if (node->left == nullptr) {
                    node->left = new BinaryTreeNode(val);
                    q.push(node->left);
                } else {
                    assert(node->right == nullptr);
                    node->right = new BinaryTreeNode(val);
                    q.push(node->right);
                    q.pop();
                }
            }
        }
    }

    void preTraverse() {
        std::stack<BinaryTreeNode *> s;
        s.push(root);

        printf("[Pre Traverse]: ");
        while (!s.empty()) {
            auto node = s.top(); s.pop();
            if (node == nullptr) continue;
            printf("%d ", node->val);
            s.push(node->right);
            s.push(node->left);
        }
        printf("\n");
    }
    void inTraverse() {
        std::stack<BinaryTreeNode *> s;
        s.push(root);

        printf("[In Traverse]: ");
        while (!s.empty()) {
            auto node = s.top();
            if (node != nullptr) {
                s.push(node->left);
                continue;
            } else {
                s.pop();
                if (s.empty()) break;
                auto node = s.top();
                s.pop();
                if (node != nullptr) {
                    printf("%d ", node->val);
                    s.push(node->right);
                }
            }
        }
        printf("\n");
    }
    void postTraverse() {
        typedef std::pair<BinaryTreeNode*, bool> NodeRecord;
        std::stack<NodeRecord*> s;
        s.push(new NodeRecord(root, false));

        printf("[Post Traverse]: ");
        while (!s.empty()) {
            auto record = s.top();
            if (record->first == nullptr) s.pop();
            else {
                if (record->second) {
                    printf("%d ", record->first->val);
                    s.pop();
                } else {
                    s.push(new NodeRecord(record->first->right, false));
                    s.push(new NodeRecord(record->first->left, false));
                    record->second = true;
                }
            }
        }
        printf("\n");
    }
    void levelTraverse() {
        std::queue<BinaryTreeNode *> q;
        q.push(root);
        printf("[Level Traverse]: ");
        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            if (node == nullptr) continue;
            printf("%d ", node->val);
            q.push(node->left);
            q.push(node->right);
        }
        printf("\n");
    }
};

0 赞同 0 条回复

Sexypig. 普通 2023年7月6日下午12:20

递归实现三种遍历方式

#include<iostream>
using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void doSth(TreeNode* node) {
    std::cout << node->val << std::endl;
}

void preTraversal(TreeNode* node) {
    if (!node)  return;
    doSth(node);
    preTraversal(node->left);
    preTraversal(node->right);
}

void midTraversal(TreeNode* node) {
    if (!node)  return;
    midTraversal(node->left);
    doSth(node);
    midTraversal(node->right);
}

void lastTraversal(TreeNode* node) {
    if (!node)  return;
    lastTraversal(node->left);
    lastTraversal(node->right);
    doSth(node);
}

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午2:03

前

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        if(root==null)
            return list;
        stack.push(root);
        while(!stack.isEmpty()){
            int size = stack.size();
            for(int i=0;i<size;i++){
                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> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if(root==null)
            return list;
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                list.add(root.val);
                root=root.right;
            }
        }
        return list;
    }
}

后

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if(root==null)
            return list;
        stack.push(root);
        while(!stack.isEmpty()){
            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 条回复

mpweixin用户普通 2023年7月4日下午12:56

java
public class Solution {
    /* 先序遍历 */
    public List<Integer> preOrderTree(TreeNode root) {
        if(root == null) {
            return new ArrayList();
        }

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

        while(tmp != null || !stack.isEmpty()) {
            while(tmp != null) {
                stack.push(tmp);
                res.add(tmp.val); //先序遍历在第一次遇到节点就打印
                tmp = tmp.left;
            }
            if(!stack.isEmpty()) {
                tmp = stack.pop();
                tmp = tmp.right;
            }
        }
        return res;
    }
    /* 中序遍历 */
    public List<Integer> inOrderTree(TreeNode root) {
        if(root == null) {
            return new ArrayList();
        }

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

        while(tmp != null || !stack.isEmpty()) {
            while(tmp != null) {
                stack.push(tmp);
                tmp = tmp.left;
            }
            if(!stack.isEmpty()) {
                tmp = stack.pop();
                res.add(tmp.val); //中序遍历在第二次遇到节点就打印
                tmp = tmp.right;
            }
        }
        return res;
    }

    /* 后序遍历 */
    public List<Integer> inOrderTree(TreeNode root) {
        if(root == null) {
            return new ArrayList();
        }

        Stack<TreeNode> stack1 = new Stack<>(); 
        Stack<TreeNode> stack2 = new Stack<>(); //储存最终打印顺序
        TreeNode tmp = root;
        List<Integer> res = new ArrayList<>();

        while(tmp != null || !stack1.isEmpty()) { //将节点以根节点、右子树、左子树的顺序压入
            while(tmp != null) {
                stack1.push(tmp);
                stack2.push(tmp);
                tmp = tmp.right;
            }
            if(!stack1.isEmpty()) {
                tmp = stack1.pop();
                tmp = tmp.left;
            }
        }

        while(!stack2.isEmpty()) {
            res.add(stack2.pop().val);
        }
        return res;
    }
}

遍历了所有节点，另外出创建了栈空间，时间和空间复杂度都为O(N)

0 赞同 0 条回复

花老爷普通 2023年6月30日上午11:05

class Solution {
    public List<Integer> traversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(res, root);
        inorder(res, root);
        postorder(res, root);
    }
    // 前序遍历（递归实现）
    private void preorder(List<Integer> res, TreeNode root) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left);
        preorder(root.right);
    }
    // 中序遍历（递归实现）
    private void inorder(List<Integer> res, TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        res.add(root.val);
        inorder(root.right);
    }
    // 后序遍历（递归实现）
    private void postorder(List<Integer> res, TreeNode root) {
        if (root == null) {
            return;
        }
        postorder(root.left);
        postorder(root.right);
        res.add(root.val);
    }
}

0 赞同 0 条回复

peach 普通 2023年6月29日上午9:51

思路

递归和非递归都给出下

代码

//时间复杂度和空间复杂度都为O(n)
// 递归，前序遍历
class Solution {
    List<Integer> res = new ArrayList();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return res;
        res.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return res;
    }
}
 //递归，中序遍历
class Solution {
    List<Integer> res = new ArrayList();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return res;
        inorderTraversal(root.left);
        res.add(root.val);
        inorderTraversal(root.right);
        return res;
    }
}
 //递归，后序遍历
class Solution {
    List<Integer> res = new ArrayList();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) return res;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        res.add(root.val);
        return res;
    }
}
 //迭代，前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList();
        if(root == null) return res; //注意，addFirst这个方法传入的root不能为null，否则空指针
        Deque<TreeNode> stack = new ArrayDeque(); //深度遍历，栈处理
        stack.addFirst(root);
        while(!stack.isEmpty()){
            root = stack.removeFirst(); //拿出root
            res.add(root.val); //加入res
            if(root.right != null) stack.addFirst(root.right); //先右后左
            if(root.left != null) stack.addFirst(root.left);
        }
        return res;
    }
}
 //迭代，后序遍历
 //和前序遍历逻辑类似，先左后右，然后再翻转一下
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList();
        if(root == null) return res;
        Deque<TreeNode> stack = new ArrayDeque();
        stack.addFirst(root);
        while(!stack.isEmpty()){
            root = stack.removeFirst();
            res.add(root.val);
            if(root.left != null) stack.addFirst(root.left);
            if(root.right != null) stack.addFirst(root.right);
        }
        Collections.reverse(res);
        return res;
    }
}
 //迭代，中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList();
        Deque<TreeNode> stack = new ArrayDeque();
        while(!stack.isEmpty() || root != null){
            while(root != null){ //不断把左子节点入栈
                stack.addFirst(root);
                root = root.left;
            }
            root = stack.removeFirst(); //走到左叶子节点，然后弹出
            res.add(root.val);
            root = root.right; //向右看一眼，继续之前逻辑
        }
        return res;
    }
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月29日上午6:10

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

        res = []

        if not root:
            return res

        stack = [root]

        while stack:
            cur = stack.pop()
            res.append(cur.val)

            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)

        return res

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

        res = []

        if not root:
            return res

        stack = []
        cur = root

        while cur or stack:
            while cur:
                stack.append(cur)
                res.append(cur.val)
                cur = cur.right

            cur = stack.pop().left

        res.reverse()
        return res

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

        res = []
        stack = []

        cur = root

        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right

        return res

三种遍历

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月28日下午10:57

非递归方式用栈来实现。后序遍历相当于先序遍历改成中右左再反过来

public static void preOrderUnRecur(Node head) {
        System.out.print("pre-order: ");
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.print(head.value + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }

    public static void inOrderUnRecur(Node head) {
        System.out.print("in-order: ");
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }

    public static void posOrderUnRecur1(Node head) {
        System.out.print("pos-order: ");
        if (head != null) {
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.left != null) {
                    s1.push(head.left);
                }
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
        System.out.println();
    }

0 赞同 0 条回复

硬核洋葱普通 2023年6月28日下午5:28

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //前序遍历
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> ans;
        TreeNode* p = root;

        while(p || !stk.empty()){
            if(p){
                ans.push_back(p->val);
                stk.push(p);
                p = p->left;
            }
            else{
                p = stk.top();
                stk.pop();
                p = p->right;
            }
        }
        return ans;
    }

    //中序遍历
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> ans;
        TreeNode* p = root;

        while(p || !stk.empty()){
            if(p){
                stk.push(p);
                p = p->left;
            }
            else{
                p = stk.top();
                stk.pop();
                ans.push_back(p->val);
                p = p->right;
            }
        }
        return ans;
    }

    //后序遍历
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> ans;
        TreeNode* p = root, *pre;

        while(p || !stk.empty()){
            if(p){
                pre = p;
                stk.push(p);
                p = p->left;
            }
            else{
                TreeNode* node = stk.top();
                if(!node->right || pre == node->right){
                    stk.pop();
                    ans.push_back(node->val);
                }
                else
                    p = node->right;
                pre = node;
            }
        }

        return ans;
    }
};

其中后序遍历稍微有点麻烦，逻辑是这样的
栈弹出一个节点的时候，需要判断它的右子树是遍历了还是没遍历。
1. 如果没遍历，此节点不出栈，令p为右孩子开始遍历右子树
2. 如果遍历了，此节点出栈，把值存到结果里面
判断是否遍历的方式是保留一个prev节点，即上一个被遍历到的节点
如果右孩子不存在或者前一个遍历到的节点prev是它的右孩子，这说明右子树没有或已经遍历完了，采取第二种处理
否则说明并没有处理右子树，采取第一种处理

0 赞同 0 条回复

yxy 普通 2023年6月27日下午10:03

前序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        stack<TreeNode*> st;

        st.push(root);
        while(st.size())
        {
            auto cur=st.top();
            st.pop();
            res.push_back(cur->val);
            if(cur->right) st.push(cur->right);
            if(cur->left) st.push(cur->left);
        }
        return res;
    }
};

后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        stack<TreeNode*> st;

        st.push(root);
        while(st.size())
        {
            auto cur=st.top();
            st.pop();
            res.push_back(cur->val);
            if(cur->left) st.push(cur->left);
            if(cur->right) st.push(cur->right);

        }
        reverse(res.begin(), res.end());
        return res;
    }
};

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        stack<TreeNode*> st;
        TreeNode* cur=root;
        while(cur||st.size())
        {
            if(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            else
            {
                auto node = st.top();
                st.pop();
                res.push_back(node->val);
                cur=node->right;
            }
        }
        return res;
    }
};

0 赞同 0 条回复

行动派小彩笔普通 2023年6月27日下午7:32

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int num):val(num),left(nullptr),right(nullptr) {}
};
void printTreeList(vector<int>& nums)
{
    for (auto num : nums)
    {
        cout << num << " ";
    }
    cout << endl;
}
// 前序遍历
vector<int> PreOrder(TreeNode* root)
{
    if (!root) return {};
    vector<int> v;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty())
    {
        TreeNode* tmp = s.top();
        s.pop();
        v.push_back(tmp->val);
        if (tmp->right) //先压右子树，后遍历右子树
            s.push(tmp->right);
        if (tmp->left)
            s.push(tmp->left); //后压左子树，先遍历左子树
    }
    return v;
}
// 中序遍历
vector<int> InOrder(TreeNode* root)
{
    if (!root) return {};
    vector<int> v;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur||!s.empty())
    {
        while (cur != nullptr) 
        {
            s.push(cur);
            cur = cur->left; 
        }
        cur = s.top();
        s.pop();
        v.push_back(cur->val);
        cur = cur->right;

    }
    return v;
}
// 后续遍历
vector<int> PostOrder(TreeNode* root)
{
    vector<int> v;
    stack<TreeNode*> s;
    TreeNode* cur=root;
    s.push(root);
    while (!s.empty())
    {
        cur = s.top();
        s.pop();
        v.push_back(cur->val);
        if (cur->left) s.push(cur->left);
        if (cur->right) s.push(cur->right);
    }
    reverse(v.begin(), v.end()); //reverse时间复杂度O(n) ，可以用于容器，数组，字符串
    return v;
}



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 << "前序遍历:" << endl;
    vector<int> preVec(std::move(PreOrder(root)));
    printTreeList(preVec);

    cout << "中序遍历:" << endl;
    vector<int> InVec(std::move(InOrder(root)));
    printTreeList(InVec);

    cout << "后序遍历:" << endl;
    vector<int> PsotVec(std::move(PostOrder(root)));
    printTreeList(PsotVec);

    cout << "层次遍历:" << endl;

    return 0;
}

1 赞同 0 条回复

残月冷骄阳普通 2023年6月27日下午6:20

public class TestT {
    //前序遍历
    //递归
    //时间复杂度O(n),空间复杂度O(n)
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    //迭代
    //时间复杂度O(n),空间复杂度O(n)
    public void preOrder2(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.println(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    //迭代的统一写法：
    //时间复杂度O(n),空间复杂度O(n)
    public void preOrder3(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
                stack.push(node);
                stack.push(null);
            } else {
                System.out.println(stack.pop().val);
            }
        }
    }


    //中序遍历
    //递归
    //时间复杂度O(n),空间复杂度O(n)
    public void midOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        midOrder(root.left);
        System.out.println(root.val);
        midOrder(root.right);
    }

    //迭代
    //时间复杂度O(n),空间复杂度O(n)
    public void midOrder2(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode node = stack.pop();
                System.out.println(node.val);
                root = node.right;
            }
        }

    }

    //迭代的统一写法：
    //时间复杂度O(n),空间复杂度O(n)
    public void minOrder3(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                if (node.right != null) {
                    stack.push(node.right);
                }
                stack.push(node);
                stack.push(null);
                if (node.left != null) {
                    stack.push(node.left);
                }
            } else {
                stack.pop();
                System.out.println(stack.pop().val);
            }
        }

    }


    //后序遍历
    //递归
    //时间复杂度O(n),空间复杂度O(n)
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
    }

    //迭代
    //时间复杂度O(n),空间复杂度O(n)
    public void postOrder2(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        LinkedList<Integer> resList = new LinkedList<>();
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            resList.add(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        while (!resList.isEmpty()) {
            System.out.println(resList.removeLast());
        }
    }


    //迭代的统一写法：
    //时间复杂度：O(n)，空间复杂度：O(n)
    public void postOrder3(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                stack.push(node);
                stack.push(null);
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            } else {
                System.out.println(stack.pop().val);
            }
        }
    }


}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年6月27日下午5:36

C++实现

#include <stack>
#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void preOrder(TreeNode* root) {
    if (root == NULL)
        return;

    stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";

        if (node->right)
            s.push(node->right);
        if (node->left)
            s.push(node->left);
    }
}

void inOrder(TreeNode* root) {
    if (root == NULL)
        return;

    stack<TreeNode*> s;
    TreeNode* p = root;

    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            s.push(p);
            p = p->left;
        }
        p = s.top();
        s.pop();
        cout << p->val << " ";
        p = p->right;
    }
}

void postOrder(TreeNode* root) {
    if (root == NULL)
        return;

    stack<TreeNode*> s1, s2;
    s1.push(root);

    while (!s1.empty()) {
        TreeNode* node = s1.top();
        s1.pop();
        s2.push(node);

        if (node->left)
            s1.push(node->left);
        if (node->right)
            s1.push(node->right);
    }

    while (!s2.empty()) {
        cout << s2.top()->val << " ";
        s2.pop();
    }
}

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 << "Preorder traversal: ";
    preOrder(root);
    cout << endl;

    cout << "Inorder traversal: ";
    inOrder(root);
    cout << endl;

    cout << "Postorder traversal: ";
    postOrder(root);
    cout << endl;

    return 0;
}

0 赞同 0 条回复

彦，，# 普通 2023年6月27日下午3:57

//前序遍历的非递归算法
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> ans;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty())
        {
            TreeNode* temp = s.top();
            s.pop();
            ans.push_back(temp->val);
            if(temp->right)
            {
                s.push(temp->right);
            }
            if(temp->left)
            {
                s.push(temp->left);
            }
        }
        return ans;
    }
// };

//中序遍历
 vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> ans;
        stack<TreeNode*> s;
        TreeNode* curr = root;
        while(curr || !s.empty())
        {
            while(curr)
            {
                s.push(curr);
                curr = curr->left;
            }
            curr = s.top();
            s.pop();
            ans.push_back(curr->val);
            curr = curr->right;
        }
        return ans;
}
//后序遍历
 vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> ans;
        stack<TreeNode*> s;
        TreeNode* pPre = NULL;  
        TreeNode* curr = root;
        s.push(curr);
        while(!s.empty())  
        {  
            curr = s.top();   //当前节点置为栈顶节点  
            if((curr->left==NULL && curr->right==NULL) ||   
                (pPre!=NULL && (curr->left==pPre || curr->right==pPre)))  
            {  
                //如果当前节点没有左右孩子，或者有左孩子或有孩子，但已经被访问输出，  
                //则直接输出该节点，将其出栈，将其设为上一个访问的节点  
                ans.push_back(curr->val);
                s.pop();
                pPre = curr;  
            }  
            else  
            {  
                //如果不满足上面两种情况,则将其右孩子左孩子依次入栈  
                if(curr->right != NULL)  
                    s.push(curr->right);  
                if(curr->left != NULL)  
                    s.push(curr->left);
            }  
        }  
    return ans;
}

0 赞同 0 条回复

Vow the vow。普通 2023年6月27日下午12:38

自己只写出了前序遍历，其他的都是借鉴其他打卡的。确实难……

// 前序遍历：中左右
    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null) return  res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        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;
    }

    // 后序遍历：左右中。反过来，是中右左
    public List<Integer> postorderTraversal2(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null) return  res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        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;
    }

    // 后序遍历：左右中
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null){
            while (root != null){
                stack.push(root);
                if(root.left != null) root = root.left;
                else root = root.right;
            }

            // 子树都遍历完了
            root = stack.pop();
            res.add(root.val);

            // 判断当前节点是左子树节点还是右子树节点
            if(!stack.isEmpty() && root == stack.peek().left){
                root = stack.peek().right;
            }else{
                root = null;
            }

        }
        return res;
    }

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

        }
        return res;
    }

0 赞同 0 条回复

屠龙手段普通 2023年6月27日上午11:49

后序遍历，需要一个标志位判断是左子树返回还是右子树。若是左子树返回则切换到右子树继续压栈，反之则出栈。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        vector res;
        stack stk;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        while(!stk.empty() || cur){
            while(cur){
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top();
            stk.pop();
            if(!cur->right || cur->right == pre){
                res.push_back(cur->val);
                pre = cur;
                cur = nullptr;
            }
            else{
                stk.push(cur);
                cur = cur->right;
            }
        }
        return res;
    }
};

先序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        vector res;
        stack stk;
        TreeNode* cur = root;
        while(!stk.empty() || cur){
            // 当前节点不为空
            while(cur){
                // 先将根节点的值加入结果集
                res.push_back(cur->val);
                // 左节点入栈
                stk.push(cur);
                cur = cur->left;    
            }
            // 上一个节点的右节点入栈
            cur = stk.top();
            stk.pop();
            cur = cur->right;
        }
        return res;
    }
};

中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector inorderTraversal(TreeNode* root) { 
        vector res;
        stack stk;
        TreeNode* cur = root;
        while(!stk.empty() || cur){
            while(cur){
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top();
            stk.pop();
            res.push_back(cur->val);
            cur = cur->right;
        }
        return res;
    }
};

0 赞同 0 条回复

张开怀普通 2023年6月27日上午10:18

前序遍历：先将根节点放入栈中，然后将右子树加入栈，再加入左子树（由于入栈先进后出，因此先放右子树，再放左子树），这样出栈的时候才是中左右的顺序

class Solution{
public:
       vector<int> preorderTraversal(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;
       }
};

中序遍历：左中右
需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素

class Solution{
public:
     vector<int> inorderTraversal(TreeNode* root){
          vector<int> result;
          stack<TreeNode*> st;
          TreeNode* cur = root;
          while(cur != NULL || !st.empty()){
               if(cur != NULL){               // 指针来访问节点，访问到最底层
                     st.push(cur);              // 将访问的节点放进栈
                     cur = cur->left;     // 左
               }else{
                     cur = st.top();        // 从栈里弹出数据，就是要处理的数据（放进result数组里的数据）
                     st.pop();
                     result.push_back(cur->val);          // 中
                     cur = cur->right;                          // 右
               }
          }
          return result;
     }
};

后序遍历：先序遍历是中左右，后序遍历是左右中
首先调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后再反转result数组，输出结果就是左右中了

class Solution{
public:
       vector<int> postorderTraversal(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 条回复

mpweixin用户永久会员 2023年6月27日上午12:03

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

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

    stack.push(root);

    while(!stack.isEmpty()){
        root = stack.pop();
        res.add(root.val);
        if(root.right != null){
            stack.push(root.right);
        }
        if(root.left != null){
            stack.push(root.left);
        }
    }

    return res;
}
//中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
    if(root == null){
        return new ArrayList<>();
    }

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


    while(!stack.isEmpty() || root != null){
        if(root != null){
            stack.push(root);
            root = root.left;
        }else{
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
    }

    return res;
}
//后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
    if(root == null){
        return new ArrayList<>();
    }

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


    while(!stack.isEmpty() || root != null){

        while(root != null){ //一直往左，左边没了，往右，走到底。
            stack.push(root);
            if(root.left != null){
                root = root.left;
            }else{
                root = root.right;
            }
        }

        //此时，左右终于完了，该自己了
        root = stack.pop();
        res.add(root.val);

        //我是左子树的话，还要先遍历右子树
        if(!stack.isEmpty() && root == stack.peek().left){
            root = stack.peek().right;
        }else{
            //我是右子树，下一个可以遍历我爹了
            root = null;
        }
    }

    return res;
}

0 赞同 0 条回复

大鑫啊普通 2023年6月26日下午11:58

二叉树前序遍历的递归和非递归代码
1、递归前序遍历

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

    public int[] preorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList();
        //递归前序遍历
        preorder(list,root);
        //返回的结果
        int[] res = new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
         return res;
    }
}

2、非递归前序遍历

public class Solution {
    public int[] preorderTraversal (TreeNode root) {
    //添加遍历结果的数组
    List<Integer> list = new ArrayList();
    Stack<TreeNode> s = new Stack<TreeNode>();
    //空树返回空数组
    if(root == null)
    return new int[0];
    //根节点先进栈
    s.push(root);
    while(!s.isEmpty()){
        //每次栈顶就是访问的元素
        TreeNode node = s.pop();
        list.add(node.val);
        //如果右边还有右子节点进栈
        if(node.right != null)
            s.push(node.right);
        //如果左边还有左子节点进栈
        if(node.left != null){
            s.push(node.left);
        }
    }
    //返回的结果
    int[] res = new int[list.size()];
    for(int i=0;i<list.size();i++)
        res[i] = list.get(i);
        return res;
    }
}

二叉树中序遍历的非递归代码

public class Solution {

    public int[] inorderTraversal (TreeNode root) {
        if(root == null)return new int[0];
        List<Integer> list = new ArrayList();
        Stack<TreeNode> s = new Stack<TreeNode>();
        //当树节点不为空或栈中有节点时
        while(root != null || !s.isEmpty()){
            while(root != null){
            s.push(root);
            root = root.left;
        }
        //访问该节点
        TreeNode node = s.pop();
        list.add(node.val);
        //进入右节点
        root = node.right;
        }
        //返回的结果
        int[] res = new int[list.size()];
        for(int i = 0;i < list.size();i++)
            res[i] = list.get(i);
        return res;
    }
}

二叉树后序遍历的非递归代码

public class Solution {
    public int[] postorderTraversal  (TreeNode root) {
        if (root == null)return new int[0];
        List<Integer> list = new ArrayList();
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode pre = null;
        //当树节点不为空或栈中有节点时
        while (root != null || !s.isEmpty()) {
            //每次先找到最左边的节点
            while (root != null) {
                s.push(root);
                root = root.left;
            }
            //访问该节点
            TreeNode node = s.pop();
            //如果该元素的右边没有或已经访问过
            if(node.right == null || node.right == pre){
                //访问中间的节点
                list.add(node.val);
                //且记录为访问过了
                pre = node;
            }else{
                //该节点入栈
                s.push(node);
                //先访问右边
                root = node.right;
            }
        }
        //返回的结果
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}

0 赞同 0 条回复

伏月三十普通 2023年6月26日下午10:15

一个统一模板
前序遍历是在左右节点处理之前就应该打印（或者是加到列表中。。。）
中序遍历是在右节点处理之前就打印
后续遍历是在左右节点处理之后打印

/**
 * 统一模板：将整个二叉树绕树一周
 */
public class E01LeetCodeAll {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(
                new TreeNode(new TreeNode(4),2,null),
                1,
                new TreeNode(new TreeNode(5),3,new TreeNode(6))
        );



        LinkedList<TreeNode> stack=new LinkedList<>();//用一个栈来辅助
        TreeNode curr=root;//代表当前节点

        TreeNode pop=null;//最近一次弹栈的元素

        while (curr!=null || !stack.isEmpty()){
            if(curr!=null){
                stack.push(curr);//压入栈，为了记住回来的路
                System.out.println("前："+curr.val);//前序遍历 在处理左子树之前就打印当前节点的值
                //处理左子树
                curr=curr.left;

            }else {
                TreeNode peek = stack.peek();//栈顶元素 要判断栈顶元素的左右子树都处理完成，才把栈顶元素弹出


                if(peek.right==null){//没有右子树
                    System.out.println("中："+peek.val);//中序遍历(在右子树处理之前打印) 没有右子树的时候也要打印
                    pop = stack.pop();
                    System.out.println("后："+pop.val);//后续遍历 左右子树处理完成后 弹栈 并打印
                    /*
                         2
                        / \
                       4   7
                       此时从7往回走，右孩子已经处理完了。2就需要弹栈
                       上一次弹栈的是7  看栈顶元素的右孩子是否是7  是  右子树处理完成 栈顶元素弹出
                     */
                } else if (peek.right==pop) {//右子树处理完成
                    pop = stack.pop();
                    System.out.println("后："+pop.val);//后续遍历 处理完右节点

                } else {//右子树不为null
                    System.out.println("中："+peek.val);//中序遍历：在处理右子树之前，打印
                    //此时的pop是当前节点的右孩子（在这种情况一直弹到根节点了）
                    //处理右子树
                    curr=peek.right;
                }
            }
        }
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年6月26日下午5:36

前序遍历

class Solution {
public:
    vector ans;
    vector preorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        stack s;
        while(cur || !s.empty()){
            // 一直向左寻找
            while(cur){
                s.push(cur);
                // 先入栈
                ans.push_back(cur->val);
                cur = cur->left;
            }
            // 处理中间节点
            cur = s.top();
            s.pop();
            // 处理右节点
            cur = cur->right;
        }
        return ans;

    }
};

后序遍历

class Solution {
public:
    vector ans;
    vector postorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        stack s;
        // 后序 左右中
        // 逆向 中右左(与前序相似)
        while(cur || !s.empty()){
            // 一直向右寻找
            while(cur){
                s.push(cur);
                ans.push_back(cur->val);
                cur = cur->right;
            }
            // 处理中间节点
            cur = s.top();
            s.pop();
            // 处理左节点
            cur = cur->left;
        }
        reverse(ans.begin(),ans.end());
        return ans;

    }
};

中序遍历

class Solution {
public:
    vector ans;
    vector inorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        stack s;
        while(cur || !s.empty()){
            // 一直向左寻找
            while(cur){
                s.push(cur);
                cur = cur->left;
            }
            // 处理中间节点
            cur = s.top();
            s.pop();
            ans.push_back(cur->val);
            // 处理右节点
            cur = cur->right;
        }
        return ans;

    }
};

0 赞同 0 条回复

Dsjh 普通 2023年6月26日下午5:36

前序遍历

“` cpp
“`

0 赞同 0 条回复

Yodl. 普通 2023年6月26日下午4:05

前序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root==NULL)
        {
            return ans;
        }
        stack<TreeNode*> s;
        TreeNode* p = root;
        s.push(p);
        while(!s.empty())
        {
            p = s.top();
            s.pop();
            ans.push_back(p->val);
            if(p->right!=NULL)
            {
                s.push(p->right);
            }
            if(p->left!=NULL)
            {
                s.push(p->left);
            }
        }
        return ans;
    }
};

中序遍历

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

后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root==NULL)
        {
            return ans;
        }
        stack<TreeNode*> s;
        TreeNode* p = root;
        s.push(p);
        while(!s.empty())
        {
            p = s.top();
            s.pop();
            ans.push_back(p->val);
            if(p->left!=NULL)
            {
                s.push(p->left);
            }
            if(p->right!=NULL)
            {
                s.push(p->right);
            }
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

0 赞同 0 条回复

Ming 普通 2023年6月26日下午3:16

利用队列的先进先出特点
前序遍历：

public static void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

中序遍历：按照“左-根-右”的顺序访问二叉树节点。首先递归处理左子树，然后将根节点加入队列，最后递归处理右子树。

public static void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        inorderTraversalHelper(root, queue); // 调用辅助函数填充队列

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " "); // 打印节点值
        }
    }

    private static void inorderTraversalHelper(TreeNode node, Queue<TreeNode> queue) {
        if (node == null) {
            return;
        }

        inorderTraversalHelper(node.left, queue); // 递归处理左子树
        queue.offer(node); // 将节点加入队列
        inorderTraversalHelper(node.right, queue); // 递归处理右子树
    }

后序遍历：从上到下，从右到左放入stack2

public static void postorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

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

        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);

            if (node.left != null) {
                stack1.push(node.left);
            }
            if (node.right != null) {
                stack1.push(node.right);
            }
        }

        while (!stack2.isEmpty()) {
            TreeNode node = stack2.pop();
            System.out.print(node.val + " ");
        }
    }

0 赞同 0 条回复

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

共以下 28 个回答

思路

代码

前序遍历

# 回答此问题取消回复

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

共以下 28 个回答

思路

代码

前序遍历

# 回答此问题 取消回复

# 回答此问题取消回复