宁永久会员 2023年3月10日下午4:07

添加的时候考虑节点是否为空

public List<Integer> pre(TreeNode root){
        //先把中间节点压入栈中，弹出，处理（右 左孩子放进去）
        if (root == null){
            return null;
        }
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (stack != null){
            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;
    }
    //中序遍历 左中右   向下走放入栈中，向上走取出来保存，再把右节点放入栈中。
    public List<Integer> mid(TreeNode root){
        if (root == null){
            return null;
        }
        List<Integer> list = new ArrayList<>();
        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();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }
    //后续遍历 左右中 可以先中右左再反转结果
    public List<Integer> after(TreeNode root){
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.add(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 条回复

lucca 普通 2023年1月4日下午4:28

迭代写法（非递归）

前序遍历：中，右，左入栈即可

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        if (root == null) return ans;
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode node = s.pop();
            ans.add(node.val);
            if (node.right != null) s.add(node.right);
            if (node.left != null) s.add(node.left);
        }
        return ans;
    }
}

中序遍历：先找到以当前节点为根的树的最左侧节点，然后输出该节点，如果该节点有右节点，就把当前节点切换为右侧节点，重复上述过程

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

后序遍历：仿照前序遍历，但是按照中、右、左出栈，然后将结果反转

 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        if (root == null) return ans;

        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        Stack<Integer> v = new Stack<>();
        while (!s.isEmpty()) {
            TreeNode node = s.pop();
            v.add(node.val);
            if (node.left != null) s.push(node.left);
            if (node.right != null) s.push(node.right);
        }

        while (!v.isEmpty()) ans.add(v.pop());
        return ans;
    }
}

0 赞同 0 条回复

如梦似歌普通 2023年1月2日下午8:01

//二叉树的先序非递归遍历算法
public static void PreOrderBiTree(TreeNode root){
        if(root == null)
            return;  //如果树为空树，则直接返回
        Stack<TreeNode> stack = new Stack<>();  //初始化一个空栈
        TreeNode p = root;  //创建一个指针p指向根结点
        TreeNode q;     //申请一个结点q，用来存放栈顶弹出的元素
stack.push(root); //根结点进栈
        while(!stack.isEmpty()){    //栈非空时迭代
            q = stack.peek();   //保存栈顶结点
            System.out.println(q.val);  //访问叶子结点
            stack.pop();    //栈顶结点出栈
            //子节点入栈，根据栈的特性，应该先入栈右子节点然后再入栈左子结点
            if(q.right != null)
                stack.push(q.right);
            if(q.left != null)
                stack.push(q.left);
        }
    }

//二叉树的中序非递归遍历算法
public static void InOrderBiTree(TreeNode root){
        if(root == null)
            return;  //如果树为空树，则直接返回
        Stack<TreeNode> stack = new Stack<>();  //初始化一个空栈
        TreeNode p = root;  //创建一个指针p指向根结点
        TreeNode q;     //申请一个结点q，用来存放栈顶弹出的元素
        while(p != null || !stack.isEmpty()){   //当p非空或者栈非空时，循环执行以下步骤
            if(p != null){  //如果p非空，则将p进栈，同时p指向该结点的左孩子
                stack.push(p);
                p = p.left;
            }else{          //如果p为空(说明遍历到了左子树中的叶子结点了)，则弹出栈顶元素并访问，同时将p指向该结点的右孩子
                q = stack.pop();    //指针q保存的是栈中弹出的结点(即该子树的根结点)，主要是为了验证结点是否还有孩子
                System.out.println(q.val);
                p = q.right;    //开始遍历该子树根结点的右子树
            }
        }
    }

//二叉树的后序非递归遍历算法(最难的!)
    public static void PostOrderBiTree(TreeNode root){
        if(root == null)
            return;  //如果树为空树，则直接返回
        Stack<TreeNode> stack = new Stack<>();  //初始化一个空栈
        TreeNode curNode;           //创建一个指针curNode表示当前访问的结点
        TreeNode lastVisitNode;     //申请一个结点lastVisitNode，表示上次访问的结点
        curNode = root;   //初始时令curNode指向树的根结点
        lastVisitNode = null; //因为初始时还没有任何结点别访问，所以置lastVisitNode为null

        while(curNode != null || !stack.isEmpty()){  //当curNode非空或者栈非空时，循环执行以下步骤
            while(curNode != null){     //当前结点非空，沿着左子树方向入栈
                stack.push(curNode);
                curNode = curNode.left;
            }
            //peek(): 返回栈顶对象但不将其移除
            curNode = stack.peek();     //获取栈顶元素
            //TODO:如果栈顶元素有右子树，并且该右子树未被访问过，则将当前指针指向其右子树
            if(curNode.right != null && curNode.right != lastVisitNode){
                curNode = curNode.right;
            }else{  //表示子树为空或者其右子树已经被访问过了
                stack.pop();  //这时可以肯定该结点要么是叶子结点，要么是左右子树都被访问完的一个根结点，所以可以直接出栈
                System.out.println(curNode.val);    //访问当前结点数据
                lastVisitNode = curNode;    //记录当前访问的节点(TODO:为什么要做这一步？:因为如果这个结点是叶子结点，但是我们并不清楚它到底是根结点的左孩子还是右孩子，如果是左孩子我们还要进一步判断它的根结点是否还有右孩子)
                curNode = null;     //最后记住一定要将当前访问的结点置为null，不然在下一次循环时该结点仍然会入栈
            }
        }
    }

0 赞同 0 条回复

PatNick 普通 2022年12月21日下午4:03

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 递归前序遍历
def preOrder1(root):
    if root == None:
        return
    print(root.val)
    preOrder1(root.left)
    preOrder1(root.right)




# 非递归前序遍历（队列）
def preOrder2(root):
    if root == None:
        return []
    # 声明一个队列
    queue = [root]

    while len(queue) != 0:
        print(queue[0].val)
        # 获取当前很节点的左右子节点
        cur = []
        if queue[0].left:
            cur.append(queue[0].left)
        if queue[0].right:
            cur.append(queue[0].right)
        # 更新queue，queue[1:]：第一个节点是当前的根结点已经弹出了，这个节点的左右子节点要放到queue[1:]前面（因为前序遍历是先输出根结点，再输出左右子节点
        # 所以在队列queue中要保证左子树的节点要在右子树的前面，同时左子树的节点中根结点要放在最前面）
        queue = cur + queue[1:]




# 递归中序遍历
def inOrder1(root):
    if root == None:
        return
    inOrder1(root.left)
    print(root.val)
    inOrder1(root.right)




# 非递归中序遍历(栈)
'''
沿着左子树遍历到None并存入栈中，第一次从栈顶弹出的是左子节点，第二次弹出的是它的根节点，然后将这个根节点的右子节点压入栈，并从头循环（从这个根节点开始沿着左子树遍历到None）
'''
def inOrder2(root):
    if root == None:
        return

    # 栈
    stack = [root]
    while len(stack) != 0:
        node = stack[-1]
        # 找到最底层的左节点
        while node.left:
            stack.append(node.left)
            node = node.left
        # 第一个pop出来的是左节点
        print(stack.pop().val)
        # 第二个pop出来的是左节点的父节点(根节点)
        if stack == []:
            break
        root_ = stack.pop()
        print(root_.val)
        if root_.right:
            stack.append(root_.right)



# 递归后序遍历
def postOrder1(root):
    if root == None:
        return
    postOrder1(root.left)
    postOrder1(root.right)
    print(root.val)


# 非递归后续遍历（栈+标记）
'''
每个节点默认标记为False（True表示已经将该节点的孩子节点入栈了），初始化栈中只有root，并且其标记为False，如果栈顶的标记为True弹出栈顶，如果栈顶标记为False，拿到栈顶，并将该节点的右、左孩子（注意先右后左）
压入栈，压栈的同时更新标记栈，此时原栈顶标记改为True
'''
def postOrder2(root):
    if root == None:
        return
    stack = [root]
    # 标记
    mark = [False]
    while len(stack) != 0:
        while mark[-1] == True:
            print(stack.pop().val)
            mark.pop()
        cur = stack[-1]
        if cur.right:
            stack.append(cur.right)
            mark.append(False)
        if cur.left:
            stack.append(cur.left)
            mark.append(False)
        mark[stack.index(cur)] = True

0 赞同 0 条回复

你有点可爱喔普通 2022年12月2日下午4:27

package Trees.tes;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author TangXiaoYang
 * @version 2022.1.3
 * @date 2022/12/2 16:18
 */
public class Test {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }

    //非递归的前序遍历
    public static List<Integer>preOder(TreeNode root){
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack  = new Stack<>();
        //放入当前结点
        stack.push(root);
        TreeNode p = root;
        while (!stack.isEmpty()){
            p = stack.pop();
            res.add(p.val);
            if (p.right!=null){
                stack.push(p.right);
            }
            if (p.left!=null){
                stack.push(p.left);
            }
        }
        return res;
    }
    public static List<Integer> post(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode p = root;
        TreeNode prev = null;
        while (p != null || !stk.isEmpty()) {
            while (p != null) {
                stk.push(p);
                p = p.left;
            }
            p = stk.pop();
            if (p.right == null || p.right == prev) {
                res.add(p.val);
                prev = p;
                p = null;
            } else {
                stk.push(p);
                p = p.right;
            }

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

}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:17

非递归方法实现：（借助栈）
前序（中左右）
Class solution{
Public:
    Vertor<int> preorderTraversal(TresNode* 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 sloution{
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(node->val); //中
            If(node->left) st.push(root->left);//左
            If(node->right) st.push(root->right); //左右 //先左再右，是中右左
        }
        Reverse(result.left(),result.right()); //中右左，reverse变成左右中（后序）
        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->next;
            }else{
                Cur = st.top();
                St.pop();
                Result.push_back(cur->val);
                Cur=cur->right;
                }
            }
            Return result;
        }
    }
}；

0 赞同 0 条回复

cute. 普通 2022年11月20日下午12:34

// 前序遍历
// 入栈：右 -> 左
// 出栈：中 -> 左 -> 右
var preorderTraversal = function(root, res=[]) {
  if(!root) return res;
  const stack = [root];
  let cur = null;
  while(stack.length) {
    cur = stack.pop();
    res.push(cur.val);
    cur.right && stack.push(cur.right);
    cur.left  && stack.push(cur.left);
  }
  return res;
}
// 后序遍历
// 入栈：左 -> 右
// 出栈：左 -> 右 -> 中
var preorderTraversal = function(root, res=[]) {
  if(!root) return res;
  const stack = [root];
  let cur = null;
  do {
    cur = stack.pop();
    res.push(cur.val);
    cur.left  && stack.push(cur.left);
    cur.right && stack.push(cur.right);
  }while(stack.length);
  return res.reverse();
}
// 中序遍历
// 入栈：左 -> 右
// 出栈：左 -> 中 -> 右
var preorderTraversal = function(root, res=[]) {
  const stack = [];
  let cur = root;
  while(stack.length || cur) {
    if(cur) {
      stack.push(cur);
      // 左
      cur = cur.left;
    } else {
      // 弹栈
      cur = stack.pop();
      res.push(cur.val);
      // 右
      cur = cur.right;
    }
  }
  return res;
}

0 赞同 0 条回复

symbol 普通 2022年11月9日下午12:47

//前序遍历递归
func preorderTraversal(root *TreeNode) (res []int) {
    var preOrder func (node *TreeNode) //定义一个函数变量
    preOrder = func (node *TreeNode){
        if node == nil{
            return
        }
        res = append(res, node.Val)
        preOrder(node.Left)
        preOrder(node.Right)
    }
    preOrder(root)
    return
}
 //前序遍历非递归
 func preorderTraversal(root *TreeNode) (res []int) {
    //定义一个装树节点的栈，并初始化
    stack := []*TreeNode{}
    for root != nil || len(stack) > 0{
        //一直到最左边
        for root != nil{
            res = append(res, root.Val)
            stack = append(stack, root)
            root = root.Left
        }
        //到达最左边了 弹出栈顶节点 去遍历该节点的右子树
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1] // 更新栈元素
        root= root.Right
    }
    return
}
//中序遍历递归
func inorderTraversal(root *TreeNode) (res []int) {
    var inOrder func (node *TreeNode)
    inOrder = func (node *TreeNode){
        if node == nil{
            return 
        }
        inOrder(node.Left)
        res = append(res, node.Val)
        inOrder(node.Right)
    }
    inOrder(root)
    return
}
//中序遍历非递归
func inorderTraversal(root *TreeNode) (res []int) {
    //定义一个栈
    stack := []*TreeNode{}
    for root != nil || len(stack) > 0{
        //左子树全部压入栈
        for root != nil{
            stack= append(stack, root)
            root = root.Left
        }
        //已经到达最左边 开始从栈顶弹出遍历  
        root = stack[len(stack)-1]
        //更新栈元素
        stack = stack[:len(stack)-1]
        //将该节点的值存入结果集
        res = append(res, root.Val)
        //再去递归右子树
        root= root.Right
    }
    return 
}
//递归版 后序遍历
func postorderTraversal(root *TreeNode) (res []int) {
    var postOrder func (node *TreeNode)
    postOrder = func (node *TreeNode ){
        if node == nil {
            return
        }
        postOrder(node.Left)
        postOrder(node.Right)
        res = append(res, node.Val)
    }
    postOrder(root)
    return 
}
//非递归版 
func postorderTraversal(root *TreeNode) (res []int) {
    stack := []*TreeNode{} //定义一个栈并初始化
    var pre *TreeNode //定义一个标志 记录是否是从右子树来的
    for root != nil || len(stack) > 0{
        //找到最左边
        for root != nil{
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1] //弹出栈顶元素
        stack = stack[:len(stack)-1] //更新栈元素
        //若 右子树为空了 或者是从右子树返回的 将该节点值存入结果集
        if root.Right == nil || pre == root.Right{
            res = append(res, root.Val)
            pre = root//更新标记
            root = nil //存值的节点不在继续遍历 所以置为nil
        }else{//否则继续遍历右子树
            stack = append(stack, root) //右子树不为空 该节点需要再次压入栈
            root = root.Right
        }
    }
    return
}

0 赞同 0 条回复

小肸永久会员 2022年11月8日上午9:49

前序遍历（中左右，借助一个栈，先将根节点加入栈中，再将右节点加入栈中，最后将左节点加入栈中，这样出栈的顺序就是中左右）。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null) {
            return res;
        }
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            res.add(node.val);
            if (node.right != null) {
                deque.push(node.right);
            }
            if (node.left != null) {
                deque.push(node.left);
            }
        }
        return res;
    }
}

后序遍历（借助前序遍历，来实现，只需改变下前序遍历的方式使结果集为中右左的顺序，最后将结果集反转，结果集的顺序就是左右中）

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null) {
            return res;
        }
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            res.add(node.val);
            if (node.left != null) {
                deque.push(node.left);
            }
            if (node.right != null) {
                deque.push(node.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}

中序遍历（有些特殊，因为中序遍历先访问左节点，所以还需借助一个指针）。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null) {
            return res;
        }
        TreeNode cur = root;
        while (cur != null || !deque.isEmpty()) {
            if (cur != null) {
                deque.push(cur);
                cur = cur.left; // 左
            } else {
                cur = deque.pop();
                res.add(cur.val); // 中
                cur = cur.right; //右
            }
        }
        return res;
    }
}

上面前、中、后三种遍历方式代码有些不统一，可以使用统一的代码模板，需要一个栈和作为标记的空节点。放上中序遍历的统一模板代码：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) {
            deque.push(root);
        }
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            if (node != null) {
                if (node.right != null) {
                    deque.push(node.right); // 右
                }
                deque.push(node); // 中
                deque.push(null); // 加入空节点用作标记
                if (node.left != null) {
                    deque.push(node.left); // 左
                }
            } else {
                res.add(deque.pop().val);
            }
        }
        return res;
    }
}

0 赞同 0 条回复

Asphyxia 普通 2022年11月7日下午11:06

前序遍历：
https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/1955565/er-cha-shu-qian-xu-bian-li-fei-di-gui-by-l7ka/
中序遍历：
https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/1955621/zhong-xu-bian-li-die-dai-by-pia7a-k-njps/
后续遍历：
前序遍历变顺序，然后反转结果数组即可

0 赞同 0 条回复

马啸天永久会员 2022年11月7日下午3:41

//前序

public class Solution {
    List<Integer> list = new ArrayList<>();

    //1.递归
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return list;
        list.add(root.val);
        if (root.left != null) preorderTraversal(root.left);
        if (root.right != null) preorderTraversal(root.right);
        return list;
    }

    //2.非递归
    public List<Integer> preorderTraversal2(TreeNode root) {
        if (root == null) return list;

        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();

        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            list.add(cur.val);
            if (cur.right != null) stack.push(cur.right);
            if (cur.left != null) stack.push(cur.left);
        }
        return list;
    }
}

//中序


public class Solution {
    //1.递归
    List<Integer> list = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return list;
        if (root.left != null) inorderTraversal(root.left);
        list.add(root.val);
        if (root.right != null) inorderTraversal(root.right);
        return list;
    }

    //2.非递归
    public List<Integer> inorderTraversal2(TreeNode root) {

        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> list=new ArrayList<>();

        while (root!=null && !stack.isEmpty()){
            while (root!=null){
                //向左边入栈
                stack.push(root);

                root=root.left;
            }
            root=stack.pop();

            list.add(root.val);

            root=root.right;
        }
        return list;
    }

    //3.非递归莫里斯遍历

    /***
     * 莫里斯遍历
     * 优点：不使用辅助空间
     * 缺点：修改了树形结构变成链表
     * 时间复杂度：找到每个前驱节点的复杂度是O（n），
     * 因为n个节点的二叉树有n-1条边，每条边只可能使用2次
     * （1次定位到节点，1次找到前驱节点），所以时间复杂度是O(n)
     * 空间复杂度O(1)
     */
    public List<Integer> inorderTraversal3(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode pre = null;
        while (root != null) {
            //如果有左子树，就将当前节点及右子树挂接在左子树最右的点上
            if (root.left != null) {
                pre = root.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                TreeNode tmp = root;
                pre.right = root;
                //root指向原来的左节点即当前的根节点
                root = root.left;
                tmp.left = null;//设置之前root的左节点为空
            } else {
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
    }

}

//后序

public class Solution {
    List<Integer> list = new ArrayList<>();

    //1.递归
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return list;
        if (root.left != null) postorderTraversal(root.left);
        if (root.right != null) postorderTraversal(root.right);
        list.add(root.val);
        return list;
    }

    /***
     * 后序遍历的思路
     * 使用pre指针，指向前一处访问的地方
     * 有左先左
     * 当访问节点right为null或者从右子树出来(root.right==pre)即是中
     */
    //2.非递归
    public List<Integer> postorderTraversal2(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();

        TreeNode cur = root, pre = null;
        if (root == null) return list;

        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.peek();
                if (root.right == null || root.right == pre) {
                    list.add(root.val);
                    pre = root;
                    stack.pop();
                    root = null;//表示已经访问过，下次循环不会选用
                } else {
                    root = root.right;
                }
            }
        }
        return list;
    }
}

0 赞同 0 条回复

浅夏的无奈普通 2022年11月6日下午11:20

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
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> 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;
    }
}

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
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;
    }
}

0 赞同 0 条回复

黎昕普通 2022年11月6日下午10:50

因为python3玩的不是很熟练，所以基本上参考了这个答案 https://leetcode.cn/problems/binary-tree-preorder-traversal/solution/tu-jie-er-cha-shu-de-si-chong-bian-li-by-z1m/

前序遍历

# 递归
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        def dfs(root:TreeNode)->List[int]:
            nonlocal res
            if not root:
                return
            res.append(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return res


# 非递归
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:return []
        res=[]
        stack=collections.deque()
        stack.append(root)
        while stack:
            node=stack.pop()
            res.append(node.val)
            # wrong answer 这里需要注意，因为栈本身是FILO的结构，所以使用自己的栈进行模拟（先序遍历）时，需要先入栈右子树，然后入栈左子树，这样出来的顺序才是对的
            # if node.left:stack.append(node.left)
            # if node.right:stack.append(node.right)
            if node.right:stack.append(node.right)
            if node.left:stack.append(node.left)
        return res

中序遍历

# 递归
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        def dfs(root:TreeNode)->List[int]:
            if not root: return
            nonlocal res
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        dfs(root)
        return res

# 非递归
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:return []
        res,stack=[],[]
        # 先序遍历的非递归非常巧妙，背下来, 太妙了，打了一边还是觉得妙
        cur=root
        while stack or cur:
            while cur:
                stck.append(cur)
                cur=cur.left
            tmp=stack.pop()
            res.append(tmp.val)
            cur=tmp.right
        return res

后序遍历

# 递归
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        def dfs(root:TreeNode)->List[int]:
            if not root:return 
            nonlocal res
            dfs(root.left)
            dfs(root.right)
            res.append(root.val)
        dfs(root)
        return res

# 非递归 逆转方式
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:return []
        res,stack=[],[]
        cur=root
        # 非递归简单版本：因为是后序遍历 左右中 ，所以可以按照 中左右的逆序来做
        while cur or stack:
            while cur:
                res.append(cur.val)
                stack.append(cur)
                cur=cur.right
            tmp=stack.pop()
            cur=tmp.left
        return res[::-1]

# 非递归 存储状态flag方式
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:return []
        # 难点在于如何判别这个node是不是已经遍历过了 有一个元组来标识 (flag,node) 其中flag=0表示还没有遍历过，flag=1表示已经遍历过了
        # 下面这种标识法的精髓我觉得在于保存了一种状态：这个节点是不是走过一次
        # 我感觉这种方法相比其他的更好理解，更像递归压栈，且不知道可以改写成相对应的前序遍历与中序遍历
        # 之前的前序非递归，是压栈res节点值，压栈stack右子树，压栈stack左子树，前序遍历这种解法是最简单的，因为不存在识别是不是遍历过的问题
        # 之前的中序非递归，首先要找到最左边的节点，可以向一种不断斜向左下角的操作方式一样
        stack,res=[(0,root)],[]
        while stack:
            flag,node=stack.pop()
            if not node:continue
            if flag==1: # 表示已经遍历过了
                res.append(node.val)
            else:
                stack.append((1,node))
                stack.append((0,node.right))    # 注意压栈的顺序
                stack.append((0,node.left))
        return res

0 赞同 0 条回复

lobort 普通 2022年11月2日下午9:40

前序遍历

// 非递归
// 方法一  辅助栈
class preOrder {
    public int[] preOrder(TreeNode root) {
        //前序遍历
        // 1、创建一个辅助栈  头节点进去
        // 2、栈弹出一个元素  这个元素的子节点 先右后左进栈   进栈-->头右左  出栈--> 头左右 == 前序遍历
        if (root == null) {
            return null;
        }
        //用队列去接收
        Stack<TreeNode> st = new Stack<>();
        ArrayList<Integer> res = new ArrayList<>();
        //头节点先进栈
        st.push(root);
        while (!st.isEmpty()) {
            //头节点出栈
            TreeNode cur = st.pop();
            //弹出就收集
            res.add(cur.val);
            //子节点先右后左进栈
            if (cur.right != null) {
                st.push(cur.left);
            }
            if (cur.left != null) {
                st.push(cur.left);
            }
        }
        //将ArrayList数组 转换为 int数组
        int[] arr = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            arr[i] = res.get(i);
        }
        return arr;
    }
}
// 方法二 辅助队列
 public int[]  preOrder(TreeNode root){
            //前序遍历
            // 1、先创建一个辅助队列 头节点先进队列
            // 2、队列头部弹出一个数 就将这个节点的左右节点进队列
            // 3、循环
            if( root == null){
                return new int[0];
            }
            //用队列去接收
            Queue<TreeNode> queue = new LinkedList<>();
            ArrayList<Integer> res = new ArrayList<>();
            //头节点先进队列
            queue.offer(root);
            while (!queue.isEmpty()){
                //头节点进栈
                TreeNode cur = queue.poll();
                //弹出就收集
                res.add(cur.val);
                //左右节点一次节点
                if (cur.left != null){
                    queue.offer(cur.left);
                }
                if (cur.right != null){
                    queue.offer(cur.left);
                }
            }
            //将ArrayList数组 转换为 int数组
            int[] arr = new int[res.size()];
            for (int i = 0; i < res.size(); i++) {
                arr[i] = res.get(i);
            }
            return arr;
        }
//递归
    public void perOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.println(root.val);
        preOrder2(root.left);
        preOrder2(root.right);
    }

中序遍历

//非递归
class inOrder{
    public void inOrder(TreeNode root){
        //中序遍历
        // 1、先创建一个辅助栈 头节点进栈
        // 2、将头节点的所有左节点进栈
        // 3、出来一个节点 就判断这个节点是否有右节点 并将右节点的所有左节点进栈
        // 4、循环
        if (root != null){
            Stack<TreeNode> st = new Stack<>();
            st.push(root);
            while (!st.isEmpty() || root !=null){
                if (root != null){
                    st.push(root);
                    root = root.left;
                }else{
                    root = st.pop();
                    System.out.println(root);
                    root = root.right;
                }
            }
        }
    }
}
//递归
class inOrder2{
    public void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        inOrder2(root.left);
        System.out.println(root.val);
        inOrder2(root.right);
    }
}

后序遍历

//非递归
//两个辅助栈
class postOrder {
    public void postOrder(TreeNode root) { //后序遍历  左右头
        // 1、创建两个栈 先将头节点放入栈1
        // 2、每次探出栈1弹出一个元素，放入栈2，如果该元素有子节点 先左后右放入栈1
        // 3、栈2收集完毕后弹出全部元素  元素进入栈2——>头右左  出栈 左右头-->后续遍历
        if (root != null) {
            Stack<TreeNode> st1 = new Stack<>();
            Stack<TreeNode> st2 = new Stack<>();
            st1.push(root);
            while (!st1.isEmpty()) {
                root = st1.pop();
                st2.push(root);
                if (root.left != null) {
                    st1.push(root);
                }
                if (root.right != null) {
                    st1.push(root);
                }
            }
            int[] res = new int[st2.size()];
            int count = 0;
            while (!st2.isEmpty()) {
                res[count] = st2.pop().val;
            }
        }

    }
}
//递归
class postOrder02{
    public void postOrder(TreeNode root){
        if (root == null){
            return;
        }
        postOrder02(root.left);
        postOrder02(root.right);
        System.out.println(root.val);
    }
}

0 赞同 0 条回复

狗蛋儿普通 2022年11月2日下午8:35

前中后序遍历

class Solution {
public:
    void firstTraveral(TreeNode* root,vector<int> &res){
        if(!root) return;
        res.push_back(root->val);
        qianTraveral(root->left,res);
        qianTraveral(root->right,res);
    }
    void midTraveral(TreeNode* root,vector<int> &res){
        if(!root) return;
        qianTraveral(root->left,res);
        res.push_back(root->val);
        qianTraveral(root->right,res);
    }
    void lastTraveral(TreeNode* root,vector<int> &res){
        if(!root) return;
        qianTraveral(root->left,res);
        qianTraveral(root->right,res);
        res.push_back(root->val);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        qianTraveral(root,res);
        return res;
    }
};

0 赞同 0 条回复

@ 普通 2022年11月2日下午7:41

一.二叉树的前序遍历

public class qxbl {
    private List<Integer> res = new ArrayList<Integer>();

    public List<Integer> preorderTraversal(TreeNode root) {

        rec(root);
        return res;
    }

    //递归的方式
    public void rec(TreeNode root){
        if(root == null)
            return;

        res.add(root.val);
        rec(root.left);
        rec(root.right);
    }

    //非递归（使用辅助栈）
    public List<Integer> notRec(TreeNode root){
        if(root == null)
            return res;
        Deque<TreeNode> stack = new ArrayDeque<>();

        stack.push(root);

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

            if(pop.right != null)
                stack.push(pop.right);

            if(pop.left != null)
                stack.push(pop.left);
        }

        return res;
    }
}

二.二叉树的中序遍历

public class zxbl {
    private List<Integer> res = new ArrayList<Integer>();

    public List<Integer> preorderTraversal(TreeNode root) {

        rec(root);
        return res;

    }

    //递归的方式
    public void rec(TreeNode root){
        if(root == null)
            return;

        rec(root.left);
        res.add(root.val);
        rec(root.right);
    }

    //非递归（使用辅助栈）
    public List<Integer> notRec(TreeNode root){
        if(root == null)
            return res;
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }

        return res;
    }

}

三.二叉树的后序遍历

public class hxbl {
    public List<Integer> res = new ArrayList<Integer>();

    public List<Integer> postorderTraversal(TreeNode root) {

        rec(root);
        return res;
    }

    //递归的方式
    public void rec(TreeNode node) {
        if (node == null) {
            return;
        }

        rec(node.left);
        rec(node.right);
        res.add(node.val);

    }

    //非递归（使用辅助栈）
    public List<Integer> notRec(TreeNode root) {
        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 class cxbl {
    private List<Integer> res = new ArrayList<Integer>();

    //使用辅助队列
    public void levelOrder(TreeNode root){
        Queue<TreeNode> que = new LinkedList<>();

        que.add(root);

        while(!que.isEmpty()){
            TreeNode node = que.remove();
            res.add(node.val);

            if(node.left != null)
                que.add(node.left);

            if(node.right != null)
                que.add(node.right);

        }
    }
}

总结:
前、中、后遍历：
思路：递归和迭代（使用辅助栈）
时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(log⁡n))，最坏情况下树呈现链状，为 O(n)。
前序遍历和后序遍历的代码思路基本一样，而中序遍历稍微有的区别。

层序遍历:
思路：迭代（使用队列）

0 赞同 0 条回复

酥合普通 2022年11月2日上午12:33

前序

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(null == root){
            return ans;
        }
        Deque<TreeNode> tmp = new LinkedList<>();
        tmp.push(root);
        while(!tmp.isEmpty()){
            TreeNode cur = tmp.pop();
            ans.add(cur.val);
            if(cur.right != null){
                tmp.push(cur.right);
            }
            if(cur.left != null){
                tmp.push(cur.left);
            }
        }
        return ans;
    }
}

中序

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> tmp = new LinkedList<>();
        TreeNode cur = root;
        while(!tmp.isEmpty() || cur != null){

            if(cur != null){
                tmp.push(cur);
                cur = cur.left;
            } else {
                cur = tmp.pop();
                ans.add(cur.val);
                cur = cur.right;
            }

        }
        return ans;

    }
}

后序

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(null == root){
            return ans;
        }
        Deque<TreeNode> tmp = new LinkedList<>();
        TreeNode prev = null;
        while(root != null || !tmp.isEmpty()){
            while(root != null){
                tmp.push(root);
                root = root.left;
            }
            root = tmp.pop();
            if(root.right == null || root.right == prev){
                ans.add(root.val);
                prev = root;
                root = null;
            }else{
                tmp.push(root);
                root = root.right;
            }
        }
        return ans;
    }
}

0 赞同 0 条回复

Tolkien 永久会员 2022年11月1日下午11:25

// 先序遍历
LinkedList<Integer> result = new LinkedList<>();

public List<Integer> preorderTraversal2(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

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

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.addFirst(node.val);

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

            if (node.right != null) {
                stack.push(node.right);
            }
        }
        return result;
    }

// 后序遍历
ArrayList<Integer> result = new ArrayList<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return result;
        }

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

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val,0);

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

// 中序遍历
 public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

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

        return result;
    }

0 赞同 0 条回复

yanshuojune 普通 2022年11月1日上午12:07

时间复杂度：O（n）
空间复杂度：O（n）

# 前序遍历
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack, res, cur_node = [], [], root
        while cur_node or stack:
            while cur_node:
                res.append(cur_node.val)
                stack.append(cur_node)
                cur_node = cur_node.left
            temp = stack.pop()
            cur_node = temp.right
        return res

# 中序遍历
if not root:
            return []
        stack, res, cur_node = [], [], root
        while cur_node or stack:
            while cur_node:
                stack.append(cur_node)
                cur_node = cur_node.left
            temp = stack.pop()
            res.append(temp.val)
            cur_node = temp.right
        return res

# 后续遍历
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # 模板解法
        if not root:
            return []
        stack, res, cur_node = [], [], root
        while stack or cur_node:
            while cur_node:
                res.append(cur_node.val)
                stack.append(cur_node)
                cur_node = cur_node.right
            temp = stack.pop()
            cur_node = temp.left
        return res[::-1]

0 赞同 0 条回复

Gg 普通 2022年10月31日下午11:17

 // 先序遍历，利用辅助栈即可
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<TreeNode> stk = new Stack<>();
        // 压栈
        stk.push(root);
        while(!stk.isEmpty()){
            // 出栈
            TreeNode curr = stk.pop();
            res.add(curr.val);

            // 压栈
            if(curr.right != null){
                stk.push(curr.right);
            }
            if(curr.left != null){
                stk.push(curr.left);
            }
        }
        return res;
    }
}
// 中序遍历,利用辅助栈，以及一个指针，进入到最左节点
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();
        TreeNode curr = root;
        while(!stk.isEmpty() || curr != null){
            if(curr != null){
                // 压栈
                stk.push(curr);
                curr = curr.left;
            }else{
                // 出栈
                curr = stk.pop();
                res.add(curr.val);
                curr = curr.right;

            }
        }
        return res;
    }
}
 // 后序遍历，利用放一个null节点标记节点加入到栈的元素
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<TreeNode> stk = new Stack<>();
        stk.push(root);
        while(!stk.isEmpty()){
            TreeNode curr = stk.pop();
            if(curr == null){
                // 为空，则下一个节点为已经遍历过的子节点的元素
                res.add(stk.pop().val);
            }else{
                // 标记该树的子节点都加入到栈
                stk.push(curr);
                stk.push(null);
                if(curr.right != null){
                    stk.push(curr.right);
                }
                if(curr.left != null){
                    stk.push(curr.left);
                }
            }
        }
        return res;

    }
}

0 赞同 0 条回复

y 普通 2022年10月31日下午9:12

//前序遍历是中左右，每次先处理的是中间节点，先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。这样左孩子才先出栈
var preorderTraversal = function(root) {
  if(!root) return []
  const stack=[];
  let res=[];
  let cur=null;
  stack.push(root)
  while(stack.length){
    cur=stack.pop()
    res.push(cur.val)
    cur.right && stack.push(cur.right);
    cur.left && stack.push(cur.left)
  }
  return res;
};
//中序遍历是左中右，先找到最底层的左孩子
var inorderTraversal = function(root) {
  if(!root) return [];
  let stack = [];
  let res = [];
  let cur = root;
  while(stack.length || cur) {
      if(cur) {
          stack.push(cur);
          cur = cur.left;
      } else {
          cur = stack.pop();
          res.push(cur.val);
          cur = cur.right;
      }
  }
  return res;
};
//后序遍历
var postorderTraversal = function(root) {
  if(!root) return [];
  let res = [];
  let stack =[root];
  while(stack.length) {
      let cur = stack.pop();
      res.push(cur.val);
      cur.left && stack.push(cur.left);
      cur.right && stack.push(cur.right);
  }
  return res.reverse();
};

0 赞同 0 条回复

T 普通 2022年10月31日下午5:50

class Solution {
    // 根左右
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        while(!deque.isEmpty()) {
            TreeNode tmp = deque.poll();
            list.add(tmp.val);
            if(tmp.right != null) deque.push(tmp.right);
            if(tmp.left != null) deque.push(tmp.left);
        }
        return list;
    }

    // 左根右
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Deque<TreeNode> deque = new LinkedList<>();
        while(root != null || !deque.isEmpty()) {
            while(root != null) {
                deque.push(root);
                root = root.left;
            }
            root = deque.poll();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }


    //左右根
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode prev = null;
        while(root != null || !deque.isEmpty()) {
            while(root != null) {
                deque.push(root);
                root = root.left;
            }
            root = deque.poll();
            if(root.right == null || root.right == prev){
                list.add(root.val);
                prev = root;
                root = null;
            } else {
                deque.push(root);
                root = root.right;
            }

        }
        return list;
    }


}

0 赞同 0 条回复

庄重普通 2022年10月31日下午3:11

//前序遍历
class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        if(root == nullptr) return vector{};

        sta.push(root);
        TreeNode* pNode = nullptr;
        while(!sta.empty()){
            pNode = sta.top();
            sta.pop();
            if(pNode != nullptr){
                if(pNode->right != nullptr){
                    sta.push(pNode->right);
                }
                
                if(pNode->left != nullptr){
                    sta.push(pNode->left);
                }
                sta.push(pNode);
                sta.push(nullptr);                
            }
            else{
                vec.push_back(sta.top()->val);
                sta.pop();
            }
        }   
        return vec;     
    }
    vector vec;
    stack sta;
};
//中序遍历
class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        if(root == nullptr) return vector{};

        sta.push(root);
        TreeNode* pNode = nullptr;
        while(!sta.empty()){
            pNode = sta.top();
            sta.pop();
            if(pNode != nullptr){
                if(pNode->right != nullptr){
                    sta.push(pNode->right);
                }
                
                sta.push(pNode);
                sta.push(nullptr);
                
                if(pNode->left != nullptr){
                    sta.push(pNode->left);
                }
            }
            else{
                vec.push_back(sta.top()->val);
                sta.pop();
            }
        }   
        return vec;     
    }
    vector vec;
    stack sta;
};
 //后序遍历
class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        if(root == nullptr) return vector{};

        sta.push(root);
        TreeNode* pNode = nullptr;
        while(!sta.empty()){
            pNode = sta.top();
            sta.pop();
            if(pNode != nullptr){
                sta.push(pNode);
                sta.push(nullptr);

                if(pNode->right != nullptr){
                    sta.push(pNode->right);
                }
                
                if(pNode->left != nullptr){
                    sta.push(pNode->left);
                }
            }
            else{
                vec.push_back(sta.top()->val);
                sta.pop();
            }
        }   
        return vec;     
    }
    vector vec;
    stack sta;
};

0 赞同 0 条回复

绍熙普通 2022年10月31日下午1:29

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
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> 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;
    }
}

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
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;
    }
}

0 赞同 0 条回复

是梦终空永久会员 2022年10月31日下午12:24

时间O(n)
空间O(n)
前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        //前序，中->左->右。定义栈迭代遍历，入栈:中->右->左
        List<Integer> list = new ArrayList<>();
        if(root == null)    return list;
        Stack<TreeNode> st1 = new Stack<>();
        st1.push(root);
        while(!st1.isEmpty()){
            TreeNode pre = st1.pop();
            list.add(pre.val);
            if(pre.right!=null) st1.push(pre.right);
            if(pre.left!=null)  st1.push(pre.left);  
        }
        return list;
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //中序：左中右 入栈顺序：左右  
        List<Integer> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Stack<TreeNode> st1 = new Stack<>();
        while(!st1.isEmpty() || root != null){    //都为空时，结束循环
            if(root != null){
                st1.push(root);
                root = root.left;
            }else{       //左节点为空时，把中节点的val添加进res，且中节点出栈，然后把右节点入栈
                root = st1.pop();
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
}

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        //后序，左右中  入栈顺序:中左右
        //和前序很像。可以先处理中间节点，然后入栈左节点，再入栈右节点，出栈为中右左，最后翻转结果，就可以得到左右中的集合了
        List<Integer> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while(!st.isEmpty()){
            TreeNode pre = st.pop();
            res.add(pre.val);
            if(pre.left!=null) st.add(pre.left);
            if(pre.right!=null) st.add(pre.right);
        }
        Collections.reverse(res);
        return res;
    }
}

模板这块感觉前序和后序比较像，就是结果翻转，中序有点差别。总的来说都是while循环和if判断。

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月31日上午11:09

要求大家掌握一下非递归的遍历方式，请大家给出自己的代码，并且认准自己的模版，以后就要这个模版，切勿变来变去
递归具有固有的局限性，如果二叉树的深度太大，那么递归代码可能会导致调用的栈溢出问题，其次递归代码太简单，面试官增加难度会要求你写非递归形式。

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Solution {
    //中序遍历非递归形式
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> nodes = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            nodes.add(cur.val);
            cur = cur.right;
        }
        return  nodes;
    }
    //前序遍历非递归形式
    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                result.add(cur.val);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return  result;
    }
    //后序遍历非递归形式
    public List<Integer> postorderTraversal(TreeNode root){
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            if (cur.right!=null && cur.right !=pre){
                cur = cur.right;
            }else {
                stack.pop();
                result.add(cur.val);
                pre = cur;
                cur = null;
            }
        }
        return result;
    }

}

0 赞同 0 条回复

天然普通 2022年10月31日上午11:08

统统都可以模版，后序遍历，如果只是和前序一样改变结点方向，得到的是根右左，然后再反转，对二叉树的中和后序的理解还不是很深刻，要理解遍历过程时间复杂度O(n),空间复杂度O(n)

#前序遍历
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res,num,stark=[],root,[]
        while num or stark:
            while num :
                res.append(num.val)
                stark.append(num)
                num = num.left
            tem = stark.pop()
            num = tem.right

        return res 

#中序遍历
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if  not root : return []
        res,stark,num = [],[],root
        while num or stark:
            while num:
                stark.append(num)
                num = num.left
            tem = stark.pop()
            res.append(tem.val)
            num = tem.right
        return res
#后序遍历
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root : return []
        res,stark,num = [],[],root
        while num or stark:
            while num :
                stark.append(num)
                res.append(num.val)
                num = num.right
            tem = stark.pop()
            num = tem.left
        return res[::-1]

0 赞同 0 条回复

So 普通 2022年10月31日上午9:39

第八天第一题

public void preOrderWithStack(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                System.out.println(node.val);
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                node = node.right;
            }
        }
    }

    public void inOrderWithStack(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                System.out.println(node.val);
                node = node.right;
            }
        }
    }

    public void postOrderWithStack(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        TreeNode lastVisit = null;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                if (node.right == null || node.right == lastVisit) {
                    System.out.println(node.val);
                    lastVisit = node;
                    node = null;
                } else {
                    stack.push(node);
                    node = node.right;
                }
            }
        }
    }

0 赞同 0 条回复

青木普通 2022年10月30日下午11:17

/**
    前序遍历
    没什么好说的
    时间复杂度O(n)
    空间复杂度O(h) h是树的高度
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> s = new ArrayDeque<>();
        TreeNode p = root;
        List<Integer> ans = new ArrayList<>();
        while(p!=null || !s.isEmpty()){
            if(p!=null){
                s.push(p);
                ans.add(p.val);
                p = p.left;
            }
            else{
                p = s.pop();
                p = p.right;
            }
        }
        return ans;
    }
}

/**
    中序遍历
    时间复杂度O(n)
    空间复杂度O(h)
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> s = new ArrayDeque<>();
        TreeNode p = root;
        List<Integer> ans = new ArrayList<>();
        while(p!=null || !s.isEmpty()){
            if(p!=null){
                s.push(p);
                p = p.left;
            }
            else{
                p = s.pop();
                ans.add(p.val);
                p = p.right;
            }
        }
        return ans;
    }
}


/**
    中序遍历 莫里斯法
    时间复杂度O(n)
    空间复杂度O(1)
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        TreeNode p = null;
        List<Integer> ans = new ArrayList<>();
        while(root!=null){
            if(root.left!=null){
                p = root.left;
                while(p.right!=null && p.right!=root){
                    p = p.right;
                }
                if(p.right==null){
                    p.right = root;
                    root = root.left;
                }
                else{
                    ans.add(root.val);
                    p.right = null;
                    root = root.right;
                }
            }
            else{
                ans.add(root.val);
                root = root.right;
            }
        }
        return ans;
    }
}


/**
    后序遍历
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> s = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        TreeNode pre = null;

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

        return ans;
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月30日下午10:06

144. 二叉树的前序遍历(10.30)

前序递归

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

前序迭代

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()){
            TreeNode cur = stack.pop();
            list.add(cur.val);
            if(cur.right != null) stack.push(cur.right);
            if(cur.left != null) stack.push(cur.left);
        }
        return list;
    }
}

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

94. 二叉树的中序遍历(10.30)

中序递归

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

中序迭代

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        while(root != null || !stack.isEmpty()){
           while(root != null){
               //向左入栈
               stack.push(root);
               root = root.left;
           }
           root = stack.pop();//左
           list.add(root.val);//根
            root = root.right; //右
        }
        return list;
    }
}

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

莫里斯遍历空间复杂度O(1)

/**
莫里斯遍历
优点：不使用辅助空间
缺点：修改了树形结构变成链表
时间复杂度:找到每个前驱节点的复杂度是 O(n)，因为 n 个节点的二叉树有 n-1 条边，每条边只可能使用 2 次(一次定位到节点，一次找到前驱节点)，故时间复杂度为 O(n)
空间复杂度：O(1)
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode pre = null;
        while(root != null){
            //如果有左子树，就将当前节点及右子树挂接在左子树最右的点上
            if(root.left != null){
                pre = root.left;
                while(pre.right != null){
                    pre = pre.right;
                }
                TreeNode tmp = root;
                pre.right = root;
                //root指向原来的左节点即当前的根节点
                root = root.left;
                tmp.left = null;//设置之前root的左节点为空
            }else{
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
    }
}

145. 二叉树的后序遍历(10.30)

后序递归

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

后序迭代

/**
后序迭代的思路：
使用pre指针指向前一处访问的地方
有左先左
当访问节点right为null 或者 从右子树出来(root.right==pre) 即是中
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root,pre = null;
        if(root == null) return list;
        while(root != null || !stack.isEmpty()){
           if(root != null){
               stack.push(root);
               root = root.left;
           }else{
               root = stack.peek();
               if(root.right == null || root.right == pre){
                   list.add(root.val);
                   pre = root;
                   stack.pop();
                   root = null;//表示已经访问过，下次循环不会选用
               }else{
                    root = root.right;
               }
           }
        }
        return list;
    }
}

迭代模板

while( 栈非空 || p 非空)
{
if( p 非空)
    {

    }
else
    {

    }
}

0 赞同 0 条回复

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

共以下 30 个回答

迭代写法（非递归）

前序遍历：中，右，左入栈即可

中序遍历：先找到以当前节点为根的树的最左侧节点，然后输出该节点，如果该节点有右节点，就把当前节点切换为右侧节点，重复上述过程

后序遍历：仿照前序遍历，但是按照中、右、左出栈，然后将结果反转

前中后序遍历

一.二叉树的前序遍历

二.二叉树的中序遍历

三.二叉树的后序遍历

四.二叉树的层序遍历

前序

中序

后序

144. 二叉树的前序遍历(10.30)

94. 二叉树的中序遍历(10.30)

莫里斯遍历空间复杂度O(1)

145. 二叉树的后序遍历(10.30)

迭代模板

# 回答此问题取消回复

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

共以下 30 个回答

迭代写法（非递归）

前序遍历：中，右，左入栈即可

中序遍历：先找到以当前节点为根的树的最左侧节点，然后输出该节点，如果该节点有右节点，就把当前节点切换为右侧节点，重复上述过程

后序遍历：仿照前序遍历，但是按照中、右、左出栈，然后将结果反转

前中后序遍历

一.二叉树的前序遍历

二.二叉树的中序遍历

三.二叉树的后序遍历

四.二叉树的层序遍历

前序

中序

后序

144. 二叉树的前序遍历(10.30)

94. 二叉树的中序遍历(10.30)

莫里斯遍历空间复杂度O(1)

145. 二叉树的后序遍历(10.30)

迭代模板

# 回答此问题 取消回复

# 回答此问题取消回复