doordie. 普通 2023年7月25日上午10:07

先序遍历

    public int[] levelOrder(TreeNode root) {
        // 判断特殊情况
        if (root == null) {
            return new int[0];
        }
        //建立一个栈 存放节点
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        // 要返回的数组
        List<Integer> res = new ArrayList<>();
        while (!stack.isEmpty()) {
            TreeNode temp = stack.pop();
            res.add(temp.val);
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }

        }
        int[] result = new int[res.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = res.get(i);
        }
        return result;
    }

中序遍历

public int[] levelOrderDFS(TreeNode root) {
//辅助栈
Stack stack = new Stack<>();
//辅助节点
TreeNode node = root;
while (node != null || !stack.isEmpty()){
//迭代访问节点的左孩子
while (node != null) {
//入栈
stack.push(node);
node = node.left;
}

            //出栈
            node = stack.pop();
            System.out.println(node.val);
            node = node.right;

    }
    return  new int[0];
}

后序遍历

  public int[] levelOrderDFS2(TreeNode root){
        // 主栈
        Stack<TreeNode> stack = new Stack<>();

        // 辅助节点 prev:记录前一个出栈的节点
        TreeNode prev = null;
        TreeNode curr = root;
        // 算法过程
        while (curr!=null || !stack.isEmpty()) {
            // 一直遍历左孩子
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            //
            curr = stack.peek();
            if(curr.right == null || curr.right == prev){
                System.out.println(curr.val);
                stack.pop();
                prev = curr;
                curr =null;
            }else {
                curr = curr.right;
            }
        }
        return new int[0];
    }

0 赞同 0 条回复

Terence💧 普通 2023年7月22日下午1:14

打印二叉树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) []int {
    res := make([]int, 0)
    if root == nil {
        return res
    }

    var queue []*TreeNode = []*TreeNode{root}
    for len(queue) != 0 {
        var temp []*TreeNode
        for i := 0; i < len(queue); i++ {
            item := queue[i]
            res = append(res, item.Val)
            if item.Left != nil {temp = append(temp, item.Left)}
            if item.Right != nil {temp = append(temp, item.Right)}
        }
        queue = temp
    }

    return res
}

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月18日下午10:30

“`java
class Solution {
public List preorderTraversal(TreeNode root) {
// 使用迭代法（非递归，用栈实现）
Stack stack = new Stack<>();
List result = new ArrayList<>();
if(root==null) return result;
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
// 处理中节点
result.add(cur.val);
// 先右后左，处理时才能先左后右
if(cur.right!=null){
stack.push(cur.right);
}
if(cur.left!=null){
stack.push(cur.left);
}
}
return result;
}

public List inorderTraversal(TreeNode root) {
// 中序遍历的迭代写法
// 访问的顺序和处理顺序不一致（前序是一致的）
// 用指针的遍历来访问元素，栈来处理节点上的元素
List result = new ArrayList<>();
Stack 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;
}

public List postorderTraversal(TreeNode root) {
// 前序是中左右，后序是左右中
// 中左右->中右左->左右中（逆序）
List result = new ArrayList<>();
Stack stack = new Stack<>();
if(rootnull) return result;
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
result.add(cur.val);
if(cur.left!=null) stack.push(cur.left);
if(cur.right!=null) stack.push(cur.right);
}
Collections.reverse(result);
return result;
}
}
时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

北辰普通 2023年7月18日下午7:21

public class 二叉树遍历的非递归代码 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        List ans = preorderTraversal(root);
        System.out.println(Arrays.asList(ans));
        List ans2 = inorderTraversal(root);
        System.out.println(Arrays.asList(ans2));
        List ans3 = postorderTraversal(root);
        System.out.println(Arrays.asList(ans3));
    }

    //二叉树先序遍历迭代写法
    public static List preorderTraversal(TreeNode root){
        //存储结果
        List res = new ArrayList<>();

        if(root==null) {
            return res;
        }

        Stack 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 static List inorderTraversal(TreeNode root){
        //存储结果
        List res = new ArrayList<>();

        if(root == null) return res;

        Stack stack = new Stack<>();
        TreeNode cur = root;
        while(cur!=null||!stack.isEmpty()) {
            if(cur!=null) {
                stack.push(cur);
                cur = cur.left;
            }else {
                TreeNode node = stack.pop();
                res.add(node.val);
                cur = node.right;
            }
        }
        return res;
    }

    //二叉树后序遍历迭代写法
    public static List postorderTraversal(TreeNode root){
        //存储结果
        List res = new ArrayList<>();

        if(root == null) return res;

        Stack 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;
    }
}

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

    public TreeNode() {}

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

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

时空间复杂度：O（n）

0 赞同 0 条回复

片言莫语普通 2023年7月18日上午11:47

栈和迭代法解决：思路：访问节点入栈，要处理的节点也入栈，但是做好标记，用null空指针标记也叫做标记法

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}


//中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
    Stack<TreeNode> st = new Stack<>();
    if (root != null) st.push(root);
    while (!st.empty()) {
        TreeNode node = st.peek();
        if (node != null) {
            st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
            if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
            st.push(node);                          // 添加中节点
            st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
        } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
            st.pop();           // 将空节点弹出
            node = st.peek();    // 重新取出栈中元素
            st.pop();
            result.add(node.val); // 加入到结果集
        }
    }
    return result;
}
}

//后序遍历
class Solution {
   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         

            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
   }
}

0 赞同 0 条回复

普通 2023年7月17日下午11:41

用栈实现

0 赞同 0 条回复

CKX 普通 2023年7月17日下午11:27

func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    stack := []*TreeNode{}
    var temp *TreeNode
    node := root
    for node != nil || len(stack) > 0 {
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if node.Right == nil || node.Right == temp {
            res = append(res, node.Val)
            temp = node
            node = nil
        } else {
            stack = append(stack, node)
            node = node.Right
        }
    }
    return res
}
func inorderTraversal(root *TreeNode) []int {
    res := []int{}
    node := root
    stack := []*TreeNode{}
    for node != nil || len(stack) > 0 {
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        node = node.Right
    }
    return res
}
func inorderTraversal(root *TreeNode) []int {
    res := []int{}
    node := root
    stack := []*TreeNode{}
    for node != nil || len(stack) > 0 {
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        node = node.Right
    }
    return res
}

时间空间O(n)

0 赞同 0 条回复

Mby 普通 2023年7月17日下午10:03

public class erchashuSanxubianli {
    //二叉树先序遍历迭代写法
    public List<Integer> preorderTraversal(TreeNode root){
        //存储遍历结果
        List<Integer> list = new ArrayList<>();

        if(root == null){
            return list;
        }
        //用于模拟操作的栈
        Stack<TreeNode> stack = new Stack<>();

        //初始化放入根节点
        stack.push(root);
        while(!stack.isEmpty()){
            //先序遍历先处理根节点
            TreeNode node = stack.pop();//
            list.add(node.val);
            //加入右节点---先加入右节点后加入左节点---从而保证出栈顺序为先左再右
            if(node.right != null) stack.push(node.right);
            //加入左节点
            if(node.left != null) stack.push(node.left);
        }
        return list;
    }

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

        Stack<TreeNode> stack2 = new Stack<>();
        stack2.push(root);
        while(!stack2.isEmpty()){
            //出栈顺序为 根-右-左
            TreeNode node2 = stack2.pop();
            list2.add(node2.val);
            if(root.left != null)stack2.push(node2.left);
            if(root.right != null)stack2.push(node2.right);

        }
        Collections.reverse(list2);//翻转链表
        return list2;
    }

    //二叉树中序遍历迭代法
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> list3 = new ArrayList<>();

        if(root == null){
            return list3;
        }
        Stack<TreeNode> stack3 = new Stack<>();
        /**********上述内容所有的遍历都一样***********/

        TreeNode cur = root;
        while (cur != null || !stack3.isEmpty() ){
            if(cur != null){//一直放左子节点，直到找到要处理的第一个左子节点
                stack3.push(cur);
                cur = cur.left;//将当前遍历的节点变为左子节点
            }else {//到达了要处理的位置
                TreeNode node3 = stack3.pop();
                list3.add(node3.val);//处理根节点-先处理根节点，然后就加入右子节点
                cur = node3.right;//将当前遍历节点变为右子节点
            }
        }
        return list3;
    }
}


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

    public TreeNode(){}

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

0 赞同 0 条回复

Mooby 普通 2023年7月17日下午4:23

八

0 赞同 0 条回复

CaCO3 永久会员 2023年7月17日下午2:36

”’java
//前序遍历
//递归法
class Solution{
public List preorderTraversal(TreeNode root){
List re = new ArrayList<>();
preorderTraversal(root,re);
return re;

}
private void preorderTraversal(TreeNode node,List<Integer> keys){
    if(node == null){
        return;
    }
    keys.add(node.val);
    preorderTraversal(node.left,keys);
    preorderTraversal(node.right,keys);
}

}

//迭代法
class Solution{
public List preorderTraversal(TreeNode root){
List res = new ArrayList<>();
if(root null){
return res;
}
Stack stack = new Stack<>();
TreeNode node = root;
while(!stack.isEmpty() || node != null){
while(node != null){
res.add(node.val);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
return res;
}
}

//迭代法前序遍历
class Solution{
public List preorderTraversal(TreeNode root){
List result = new LinkedList<>();
Stack st = new Stack<>();
if(root != null){
st.push(root);
}
while(!st.empty()){
TreeNode node = st.peek();
if(node != null){
st.pop();
if(node.right != null){
st.push(node.right);
}
if(node.left != null){
st.push(node.left);
}
st.push(node);
st.push(null);
}else{
st.pop();
node = st.peek();
st.pop();
result.add(node.val);
}
}
return result;
}
}
//后序遍历
//递归法
class Solution{
public List postorderTraversal(TreeNode root){
List re = new ArrayList<>();
postorderTraversal(root,re);
return re;
}
public void postorderTraversal(TreeNode root,List re){
if(root null){
return;
}
postorderTraversal(root.left,re);
postorderTraversal(root.right,re);
re.add(root.val);

}

//迭代法
class Solution{
public List postorderTraversal(TreeNode root){
List res = new ArrayList<>();
if(root null){
return res;
}
Stack stack = new Stack<>();
TreeNode prev = null;
while(root != null || !stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if(root.right null || root.right prev){
res.add(root.val);
prev = root;
root = null;
}else{
stack.push(root);
root = root.right;
}
}
return res;
}
}
//中序遍历
//递归
class Solution {
public List inorderTraversal(TreeNode root) {
List re = new ArrayList<>();
inorderTraversal(root,re);
return re;
}
public void inorderTraversal(TreeNode root,List re){
if(root null){
return;
}
inorderTraversal(root.left,re);
re.add(root.val);
inorderTraversal(root.right,re);
}
}

//迭代
class Solution{
public List inorderTraversal(TreeNode root){
List re = new ArrayList<>();
Stack stack = new Stack<>();
if(root null){
return re;
}
while(!stack.isEmpty() || root != null){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
re.add(root.val);
root = root.right;
}
return re;
}
}
时间复杂度：O(n)
空间复杂度O(n)

”’

0 赞同 0 条回复

#00456B 普通 2023年7月16日下午11:51

二叉树的遍历
以下会通过递归和迭代两种方法来实现二叉树的遍历，并通过前中后序三种方式来表达。
首先给出前序、后序、中序三种情况在leetcode上对应的题目。
二叉树的前序遍历
 二叉树的后序遍历
 二叉树的中序遍历

递归

首先，递归需要记住以下三个步骤，可以解决大部分的递归问题的逻辑：
1. 确定递归函数的参数和返回值： 明确哪些参数是要参与递归过程的，以及确定每次递归的返回值。
2. 确定终止条件： 如果递归没有终止，那么就会造成溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要完成的内容。

前序遍历

思路

确定递归函数的参数和返回值：因为需要将答案记录在vector\<int>中，所以需要在函数定义的时候加上这个数组，其他的不需要额外处理，所以函数类型为void，每次递归就是返回一个数组就好。
确定终止条件：就是当前遍历到的节点是NULL时，结束当前遍历过程。
确定单层递归的逻辑：因为是前序遍历，所以是一个左中右的进入顺序，所以先将当前节点存入数组，然后对左子树和右子树进行遍历。

代码

class Solution {
public:
    void traversal(TreeNode* root, vector<int>& vec){
        if(root == NULL){
            return ;
        }
        vec.push_back(root->val);
        traversal(root->left, vec);
        traversal(root->right, vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        traversal(root, ans);
        return ans;
    }
};

后序遍历

思路

和前序遍历一样，进行三个步骤的思考。基本一致，就是在单层逻辑上用后序遍历的思想，按照左右中的顺序。

代码

class Solution {
public:
    void traversal(TreeNode* root, vector<int>& vec){
        if(root == NULL){
            return ;
        }
        traversal(root->left, vec);
        traversal(root->right, vec);
        vec.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {    
        vector<int> ans;
        traversal(root, ans);
        return ans;
    }
};

中序遍历

思路

一致。使用中序遍历的顺序，左中右进行输入。

代码

class Solution {
public:
    void traversal(TreeNode* root, vector<int>& vec){
        if(root == NULL){
            return ;
        }
        traversal(root->left, vec);
        vec.push_back(root->val);
        traversal(root->right, vec);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        traversal(root, ans);
        return ans;
    }
};

迭代（非递归）

递归的实质就是每一次递归都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后在递归返回的时候，栈顶弹出上一次递归的各项参数，所以这就是递归可以返回上一层位置的原因。
所以这里我们也可以用栈来实现二叉树的前中后序遍历。

前序遍历

思路

前序遍历是中左右，每次先处理中间节点，所以先加入根节点，然后放入右节点，最后放入左节点。
为什么明明是中左右的顺序，但是在进入栈的时候要中右左呢？
因为根节点在入栈之后最先出栈了，完成了中左右的中。但是左右子树还要分别向下迭代，由于栈是先进后出的，所以需要让左先出栈的话，右子树需要先进入栈中。

代码

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> ans;
        if(root == NULL){//根节点为空，直接结束
            return ans;
        }
        stk.push(root);
        while(!stk.empty()){
            TreeNode* node = stk.top();
            stk.pop();
            ans.push_back(node->val);// 中
            if(node->right){
                stk.push(node->right);// 右（NULL）不入栈
            }
            if(node->left){
                stk.push(node->left);// 左（NULL）不入栈
            }
        }
        return ans;
    }
};

后序遍历

思路

前序遍历是中左右，后序遍历是左右中，这里可以通过几次变换得到。
前序遍历：中左右。
通过调换左右的入栈顺序可以得到中间过程：中右左
然后进行整个数组的反转可以得到：左右中，即后序遍历

代码

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> ans;
        if(root == NULL){//根节点为空
            return ans;
        }
        stk.push(root);
        while(!stk.empty()){
            TreeNode* node = stk.top();
            stk.pop();
            ans.push_back(node->val);// 中
            if(node->left){
                stk.push(node->left);// 左
            }
            if(node->right){
                stk.push(node->right);//右
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

中序遍历

思路

中序遍历的过程和前序后序不太一样，由于不是先处理中，但是得先运行到中，即处理和运行顺序不一致，所以不好直接对中进行简单处理。这里需要用指针来进行遍历。由于中序遍历是左中右，所以要先遍历到左子树的最左下角的节点，然后再进行输出，期间要保存每个路径的节点信息到数组。

代码

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> ans;
        if(root == NULL){
            return ans;
        }
        TreeNode* cur = root;
        while(cur || !stk.empty()){
            if(cur){//cur不为空，进入栈
                stk.push(cur);
                cur = cur->left;
            }
            else{
                cur = stk.top();//此前cur已经是NULL，所以现在要回到父节点，然后对右节点进行判断，同时输出父节点
                stk.pop();
                ans.push_back(cur->val);
                cur = cur->right;
            }
        }
        return ans;
    }
};

1 赞同 0 条回复

神经蛙普通 2023年7月16日下午4:54

/**
    前序遍历
    根-左-右
    用栈来模拟递归操作
*/
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        if (root == null) {
            return res;
        }

        stack.add(root);

        while(!stack.isEmpty()) {
            TreeNode node = stack.removeLast();
            res.add(node.val);
            if (node.right != null) {
                stack.add(node.right);
            }
            if (node.left != null) {
                stack.add(node.left);
            }
        }

        return res;
    }
}
/**
    中序遍历
    左-根-右
    用栈来模拟递归操作
*/
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        if (root == null) {
            return res;
        }

        TreeNode node = root;

        while(node != null || !stack.isEmpty()) {
            // 一直到左子树为null
            while(node != null) {
                stack.add(node);
                node = node.left;
            }
            node = stack.removeLast();
            res.add(node.val);
            node = node.right;
        }

        return res;

    }
}
/**
    后序遍历
    左-右-根
    用栈来模拟递归操作
*/
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        if (root == null) {
            return res;
        }

        TreeNode node = root;
        TreeNode prev = null;

        while(node != null || !stack.isEmpty()) {
            // 一直将左节点入栈
            while(node != null) {
                stack.add(node);
                node = node.left;
            }

            // 拿到栈顶元素
            node = stack.removeLast();
            // 如果node的右子树是null或者右子树被遍历了
            if (node.right == null || node.right == prev) {
                res.add(node.val);
                prev = node;
                node = null;
            } else {
                // 右子树不为null 同时 右子树没被遍历
                stack.add(node);
                node = node.right;
            }

        }

        return res;
    }
}

0 赞同 0 条回复

Marshan 普通 2023年7月16日下午2:53

前序

vector<int> preorderTraversal(TreeNode *root){
    vector<int> result;
    if(root == nullptr){
        return result;
    }
    stack<TreeNode *>nodeStack;
    nodeStack.push(root);

    while(!nodeStack.empty()){
        auto currNode = nodeStack.top();
        nodeStack.pop();
        result.push_back(currNode->val);

        if(currNode->right){
            nodeStack.push(currNode->right);
        }

        if(currNode->left){
            nodeStack.push(currNode->left);
        }
    }
    return result;
}

中序

vector<int> inorderTraversal(TreeNode *root){
    vector<int> result;
    if(root == nullptr){
        return result;
    }
    stack<TreeNode *>nodeStack;
    TreeNode *currNode = root;
    while(currNode != nullptr || !nodeStack.empty()){
        while(currNode != nullptr){
            nodeStack.push(currNode);
            currNode = currNode->left;
        }

        currNode = nodeStack.top();
        nodeStack.pop();
        result.push_back(currNode->val);

        currNode = currNode->right;
    }
    return result;
}

后序

vector<int> postorderTraversal(TreeNode *root){
    vector<int> result;
    if(root == nullptr){
        return result;
    }

    stack<TreeNode *>nodeStack;
    TreeNode *currNode = root;
    TreeNode *lastVisitedNode = nullptr;

    while(currNode != nullptr || !nodeStack.empty()){
        if(currNode != nullptr){
            nodeStack.push(currNode);
            currNode = currNode->left;
        }
        else{
            TreeNode *topNode = nodeStack.top();
            if(topNode->right != nullptr && topNode->right != lastVisitedNode){
                currNode = topNode->right;
            }
            else{
                nodeStack.pop();
                result.push_back(topNode->val);
                lastVisitedNode = topNode;
            }
        }
    }
    return result;
}

0 赞同 0 条回复

波雅汉库克普通 2023年7月16日上午11:55

Preorder
1) 递归：

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

2) 迭代

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

Inorder
1) 递归

class Solution {
public:
    void inOrder(TreeNode* root, vector<int>& res){
        if(root == nullptr){
            return;
        }
        if(root->left!=nullptr){
            inOrder(root->left, res);
        }
        res.push_back(root->val);
        if(root->right!=nullptr){
            inOrder(root->right, res);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == nullptr){
            return res;
        }
        inOrder(root, res);
        return res;
    }
};

2) 迭代

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

PostOrder
1) 递归

class Solution {
public:
    void postOrder(TreeNode* root, vector<int>& res){
        if(root == nullptr){
            return;
        }       
        postOrder(root->left, res);
        postOrder(root->right,res);
        res.push_back(root->val);

    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postOrder(root, res);
        return res;
    }
};

2) 迭代

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

0 赞同 0 条回复

阿尚普通 2023年7月16日上午12:42

//二叉树遍历非递归
//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) return result;

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

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

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

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

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

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            //与前序遍历相反，先左再右
            if(node.left != null) stack.push(node.left);
            if(node.right != null) stack.push(node.right);
        }
        reverse(result);//也可用Collection来实现翻转

        return result;
    }

    public void reverse(List<Integer> list){
        int left = 0;
        int right = list.size() - 1;

        while(left < right){
            Integer temp = list.get(left);
            list.set(left, list.get(right));
            list.set(right, temp);

            left++;
            right--;
        }
    }
}

//中序遍历
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(!stack.isEmpty() || cur != null){

            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                TreeNode node = stack.pop();
                result.add(node.val);
                cur = node.right;
            }
        }

        return result;
    }
}

0 赞同 0 条回复

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

共以下 15 个回答

先序遍历

中序遍历

后序遍历

递归

前序遍历

思路

代码

后序遍历

思路

代码

中序遍历

思路

代码

迭代（非递归）

前序遍历

思路

代码

后序遍历

思路

代码

中序遍历

思路

代码

# 回答此问题取消回复

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

共以下 15 个回答

先序遍历

中序遍历

后序遍历

递归

前序遍历

思路

代码

后序遍历

思路

代码

中序遍历

思路

代码

迭代（非递归）

前序遍历

思路

代码

后序遍历

思路

代码

中序遍历

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复