HU 普通 2024年3月15日上午9:28

// 前序遍历
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    const res = [];

    // 先判断特殊情况
    if(root == null) return res;

    // 前序遍历，栈里面先储存根节点
    let stack = [root];

    let curr = null;

    while(stack.length) {
        // 先弹出根节点
        curr = stack.pop();

        // 再存储进res中
        res.push(curr.val);

        if(curr.right) {
            stack.push(curr.right);
        }
        if(curr.left) {
            stack.push(curr.left);
        }
    }

    return res;
};

0 赞同 0 条回复

紫芝普通 2024年3月14日下午10:24

// 前序遍历

“`c++
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
if (root == nullptr) return {};
vector res;
stack st;
TreeNode* cur = root;
while (cur || !st.empty()) {
if (cur) {
st.push(cur);
res.push_back(cur->val);
cur = cur->left;
} else {
cur = st.top();
st.pop();
cur = cur->right;
}
}
return res;

};

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

    }
};

// 后序遍历

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

0 赞同 0 条回复

Jimmy 普通 2024年3月12日下午10:06

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 //前序遍历
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(root)st.push(root);
        while(!st.empty()){
            TreeNode *node = st.top();
            if(node != nullptr){
                st.pop();
                if(node->right)st.push(node->right);
                if(node->left)st.push(node->left);
                st.push(node);
                st.push(nullptr);
            }
            else{
               st.pop();
               node = st.top();
               result.push_back(node->val);
               st.pop(); 
            }
        } 
        return result;
    }
};

//中序遍历
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(root)st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            if(node != nullptr){
                st.pop();
                if(node->right)st.push(node->right);
                st.push(node);
                st.push(nullptr);
                if(node->left)st.push(node->left);
            }
            else{
                st.pop();
                node = st.top();
                result.push_back(node->val);
                st.pop();
            }
        }
        return result;
    }
};

//后序遍历
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(root)st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            if(node != nullptr){
                st.pop();
                st.push(node);
                st.push(nullptr);
                if(node->right)st.push(node->right);
                if(node->left)st.push(node->left);
            }
            else{
                st.pop();
                node = st.top();
                result.push_back(node->val);
                st.pop();
            }
        }
        return result;
    }
};

0 赞同 0 条回复

Let it be 永久会员 2024年3月12日下午9:34

class Solution {
public int[] decorateRecord(TreeNode root) {
Queue queue = new LinkedList();
queue.add(root);
ArrayList val = new ArrayList();
while(!queue.isEmpty()){
TreeNode node = queue.poll();
val.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
int[] res = new int[val.size()];
for(int i = 0; i < val.size();i++){
res[i] = val.get(i);
}
return res;
}
}时间空间复杂度O（n）

0 赞同 0 条回复

东普通 2024年3月12日下午8:17

~~~java
//非递归
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
public List preorderTraversal(TreeNode root) {
List result = new ArrayList<>();
if (root null){
return result;
}
Stack 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 inorderTraversal(TreeNode root) {
List result = new ArrayList<>();
if (root null){
return result;
}
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;
}
}

// 后序遍历顺序左-右-中入栈顺序：中-左-右出栈顺序：中-右-左，最后翻转结果，相比于就是把前序的左右节点入栈顺序反一下，并将最后结果反转。
class Solution {
public List postorderTraversal(TreeNode root) {
List result = new ArrayList<>();
if (root null){
return result;
}
Stack 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;
}
}
java

0 赞同 0 条回复

言之命至普通 2024年3月11日下午8:09

前序：

```java
//非递归
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        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;
    }
}

中序遍历

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        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 List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        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;
    }

“`

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月11日下午6:27

我写一下递归的代码吧。
class Solution {
public List preorderTraversal(TreeNode root) {
List result = new ArrayList();
preorder(root, result);
return result;
}

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

}
// 中序遍历·递归
class Solution {
public List inorderTraversal(TreeNode root) {
List res = new ArrayList<>();
inorder(root, res);
return res;
}

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

}
// 后序遍历·递归
class Solution {
public List postorderTraversal(TreeNode root) {
List res = new ArrayList<>();
postorder(root, res);
return res;
}

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

}

0 赞同 0 条回复

mpweixin用户普通 2024年3月11日下午2:59

二叉树定义

```
  /**
 * 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<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        } 
        return ret;
    }
}

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        dns(root,0);
        return list;
    }
    public void dns(TreeNode node,int lever){
        if(node == null) return;
        if(list.size()==lever) list.add(new ArrayList<Integer>());
        list.get(lever).add(node.val);
        dns(node.left,lever+1);
        dns(node.right,lever+1);
    }
}

前序遍历

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

    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);//只有这里不一样
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

//非递归
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        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<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        preorder(root.left, res);
        res.add(root.val);//只有这里不一样
        preorder(root.right, res);
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
                res.add(node.val);//只有这里不一样
            node = node.right;
        }
        return res;
    }
}

后序遍历

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

    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        preorder(root.left, res);
        preorder(root.right, res);
        res.add(root.val);//只有这里不一样
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        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;
    }
}

0 赞同 0 条回复

方铎码农普通 2024年3月11日下午2:34

前序遍历

//非递归版前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;

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

时间复杂度$O(n)$，空间复杂度$O(n)$

中序遍历

//中序遍历的迭代方法
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

时间和空间复杂度同上

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        List<Integer> res = new ArrayList<Integer>();
        if(root == null) return res;

        TreeNode prev = null;
        while(!stack.isEmpty() || root != null){
            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;
    }
}

注意前序指针prev，因为后序遍历是

0 赞同 0 条回复

神经蛙普通 2024年3月10日下午11:02

前序遍历：
class Solution {
public:
stack<TreeNode> st;
vector res;
vector preorderTraversal(TreeNode root) {
if(root nullptr) return res;
st.push(root);
while(!st.empty())
{
TreeNode *node = st.top();
st.pop();

        res.push_back(node->val);
        if(node->right) st.push(node->right);
        if(node->left)  st.push(node->left);
    }
    return res;
}

};
后序遍历：
class Solution {
public:
vector postorderTraversal(TreeNode* root) {
stack<TreeNode> st;
vector result;
if (root NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode node = st.top();
st.pop();
result.push_back(node->val);
if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序（空节点不入栈）
if (node->right) st.push(node->right);
}
reverse(result.begin(), result.end());
return result;
}
};
中序遍历：
class Solution {
public:
vector inorderTraversal(TreeNode* root) {
vector result;
stack<TreeNode> st;
TreeNode cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
result.push_back(cur->val);
cur = cur->right;
}
}
return result;
}
};

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月10日下午3:43

// 前序遍历（非递归版）
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }

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

        stack.push(root);
        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);
            }
        }

        return res;
    }
}

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

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

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

        return res;
    }
}

// 后序遍历(非递归）
class Solution {
    List<Integer> res = new ArrayList<>();

    // 时间 O(n) 空间 O(n)
    public List<Integer> postorderTraversal(TreeNode root) {

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

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


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

        }
        return res;
    }
}

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月10日上午10:56

class Solution {
public:
    // 前序
    // 总是先把右孩子入栈，然后再把左孩子入栈，这样出栈的时候，总是左先出
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        stack<TreeNode*> stk;

        stk.push(root);
        while(!stk.empty()) {
            TreeNode* cur = stk.top(); stk.pop();
            res.emplace_back(cur->val);
            if(cur->right) stk.push(cur->right);
            if(cur->left) stk.push(cur->left);
        }
        return res;
    }

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

    // 后序
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        stack<TreeNode*> stk;

        while(root || !stk.empty()) {
            if(root) {
                stk.push(root);
                if(root->left) root = root->left;
                else root = root->right;
            } else {
                 // 此处出栈操作
                root = stk.top(); stk.pop();
                res.emplace_back(root->val);

                // 如果刚才出栈的那个节点是左孩子，那么下一步就要遍历他的父亲的右孩子；
                // 若是右孩子，则出栈父亲，即让root=nullptr，直接快进到出栈的代码
                if(!stk.empty() && stk.top()->left == root) root = stk.top()->right;
                else root = nullptr;
            }
        }
        return res;
    }
};

0 赞同 0 条回复

Yuki 永久会员 2024年3月10日上午10:24

打卡
https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/2677830/fei-di-gui-de-er-cha-shu-qian-zhong-hou-q5u54

0 赞同 0 条回复

Yox 普通 2024年3月10日上午5:36

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

class Solution:
def decorateRecord(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
tmp = []
res = []
tmp.append(root)
while tmp:
cur = tmp.pop(0)
res.append(cur.val)
if cur.left: tmp.append(cur.left)
if cur.right: tmp.append(cur.right)
return res

双 o n

0 赞同 0 条回复

云无深雁影普通 2024年3月10日上午1:23

//后续
class Solution {
public List postorderTraversal(TreeNode root) {
List ans = new ArrayList<>();
Stack stack = new Stack<>();
TreeNode pre =new TreeNode();
while(root!=null || !stack.empty()){
while(root!=null){//先遍历所有左节点，确保栈出来的节点的左节点都遍历过了
stack.push(root);
root = root.left;
}
root = stack.peek();
if(root.right null || root.right pre){//只有右节点遍历过或者没有右节点的父节点才能被出栈
ans.add(root.val);
pre = root;
root = null;
stack.pop();
}
else
root = root.right;

    }
    return ans;

}

}

//中序
class Solution {
public List inorderTraversal(TreeNode root) {
//莫里斯遍历
List ans = new ArrayList<>();
TreeNode
if(root null)
return ans;
while(root!=null){
if(root.left!=null){
TreeNode temp = root.left;
while(temp.right!=null)//找到最右子节点
temp = temp.right;
temp.right = root;
temp = root.left;
root.left = null;
root = temp;
}
else{//没有左子，直接输出
ans.add(root.val);
root = root.right;
}

    }
    return ans;

}

}

//前序
class Solution {
public List preorderTraversal(TreeNode root) {
//非递归写法
Stack stack = new Stack<>();
List ans = new ArrayList<>();
if(root null) return ans;
stack.push(root);
while(!stack.empty()){
TreeNode temp = stack.pop();
ans.add(temp.val);
if(temp.right!=null) stack.push(temp.right);
if(temp.left!=null) stack.push(temp.left);
}
return ans;
}
}

0 赞同 0 条回复

机电皮怪永久会员 2024年3月9日下午11:02

“`C++
#include
#include
#include

using namespace std;

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

class Solution {
public:
//先序遍历迭代模式
vector preorderTraversal(TreeNode* root) {
stack<TreeNode> sub;
vector result;
TreeNode cur = root;
do
{
//向左下遍历，并且先访问
while (cur != nullptr)
{
result.push_back(cur->val);
sub.push(cur);
cur = cur->left;
}

        //看看左下角有没有右子树
        if (sub.empty() == false)
        {
            cur = sub.top();
            sub.pop();
            cur = cur->right;
        }

    } while (cur != nullptr || sub.empty() == false );

    return result;
}

// 中序遍历非递归形式
vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> sub;
    vector<int> result;
    TreeNode* cur = root;

    do
    {
        //出栈时节点入容器
        while (cur != nullptr)
        {
            sub.push(cur);
            cur = cur->left;
        }
        if (sub.empty() == false)
        {
            cur = sub.top();
            sub.pop();
            result.push_back(cur->val);
            cur = cur->right;
        }


    } while (cur != nullptr || sub.empty() == false);

    return result;
}

// 后序遍历非递归形式
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> sub;
    vector<int> result;
    TreeNode* cur = root;
    TreeNode* pre = nullptr;

    do
    {
        //遍历右子树访问元素
        while (cur != nullptr)
        {
            sub.push(cur);
            cur = cur->left;
        }
        if (sub.empty() == false)
        {
            cur = sub.top();
            //如果右子树没被访问，访问右子树
            //有没有访问右子树用pre记录
            if (cur->right != nullptr && cur->right != pre )
            {
                cur = cur->right;
            }
            else
            {
                pre = cur;
                result.push_back(cur->val);
                sub.pop();
            }
        }
    } while (cur != nullptr || sub.empty() == false );

    return result;
}

};

int main()
{
return 0;
}

“`

0 赞同 0 条回复

王位詮釋普通 2024年3月9日下午9:53

//前序遍历：
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if(root!=null){
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode temp = stack.pop();
                result.add(temp.val);
                if(temp.right!=null){
                    stack.push(temp.right);
                }
                if(temp.left!=null){
                    stack.push(temp.left);
                }
            }
        }
        return result;
    }
}
思路：使用栈辅助，由于前序遍历是中左右，也就是说访问的节点就是要处理的节点，所以直接访问到哪个节点就加入动态数组，加入之后需要将子节点加入栈里，由于展示先进后出所以先将右子节点加入栈，然后再将左子节点加入栈。

//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        if(root!=null){
            while(!stack.isEmpty()||cur!=null){
                while(cur!=null){
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode temp = stack.pop();
                result.add(temp.val);
                if(temp.right!=null){
                    cur = temp.right;
                }
            }
        }
        return result;
    }
}
思路：中序遍历顺序是：左中右，访问的节点和处理的节点不一致，每次都应该先找到最左边的节点，所以需要指针来辅助

//后续遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root!=null){
            deque.push(root);
            while(!deque.isEmpty()){
                TreeNode temp = deque.pop();
                result.add(temp.val);
                if(temp.left!=null){
                    deque.push(temp.left);
                }
                if(temp.right!=null){
                    deque.push(temp.right);
                }
            }
        }
        Collections.reverse(result);
        return result;
    }
}
思路：把前序遍历的代码顺序改一下，从中左右 --> 中右左 然后获得的结果反转一下就是后序遍历的顺序：左右中。

0 赞同 0 条回复

heathhou 普通 2024年3月9日下午9:40

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

class Solution {
public:
    // 先序遍历非递归形式
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> s;
        TreeNode* cur = root;

        do{
            // 1、如果当前节点不为空，则一路往左下走，并且先访问后入栈
            while(cur != nullptr){
                result.push_back(cur->val);
                s.push(cur);
                cur = cur->left;// 左下
            }
            // 2、查看栈顶的节点是否有右子树
            // 入栈的时候访问节点
            if(!s.empty()){
                cur = s.top();
                s.pop();
                cur = cur->right;
            }
            // 3、如果有右子树，说明它也是个二叉树。则需要重新一路往左下走（转到1）
            // 如果没有右子树，说明这个节点已经没用了，继续判断栈是否还有元素，继续判断栈顶元素的右子树
        }while(cur != nullptr || !s.empty());

        return result;
    }
    // 中序遍历非递归形式
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> s;
        TreeNode* cur = root;

        do{
            while(cur != nullptr){
                s.push(cur);
                cur = cur->left;
            }
            // 出栈的时候访问节点
            if(!s.empty()){
                cur = s.top();
                s.pop();
                result.push_back(cur->val);
                cur = cur->right;
            }
        }while(cur != nullptr || !s.empty());

        return result;
    }

    // 后序遍历非递归形式
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;

        do{
            while(cur != nullptr){
                s.push(cur);
                cur = cur->left;
            }

            if(!s.empty()){
                // 暂存栈顶节点，是否需要访问该节点还需要进一步判断它的右子树是否已经访问过了
                cur = s.top();
                // 右子树是否被访问过，就通过pre这个指针来判断。
                // 如果pre指向的节点与右孩子指向的是同一个节点，表明右子树刚刚被访问
                // 如果栈顶节点的右子树为空，并且没有被访问过，则需要先访问右子树
                if(cur->right != nullptr && cur->right != pre){
                    cur = cur->right;
                }
                // 此时表示栈顶节点的右子树为空，或者右子树已经被访问过了，那么现在可以访问栈顶节点了
                else{
                    // 访问栈顶节点
                    result.push_back(cur->val);
                    s.pop();
                    // 更新前驱节点，方便以后判断别的节点的右子树，是不是这个刚刚访问的这个节点
                    pre = cur;
                    cur = nullptr;

                }

            }
        }while(cur != nullptr || !s.empty());
        return result;
    }
};


int main(){
    std::cout << "hello 世界" << std::endl;
    return 0;
}

0 赞同 0 条回复

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

共以下 18 个回答

二叉树定义

层序遍历

前序遍历

中序遍历

后序遍历

前序遍历

中序遍历

后序遍历

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

# 回答此问题取消回复

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

共以下 18 个回答

二叉树定义

层序遍历

前序遍历

中序遍历

后序遍历

前序遍历

中序遍历

后序遍历

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

# 回答此问题 取消回复

# 回答此问题取消回复