Open youngyangyang04 opened 5 months ago
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> st = new Stack<>();
if (root == null) return res;
st.push(root);
while (!st.isEmpty()) {
TreeNode node = st.pop();
res.add(node.val);
if (node.right != null) st.push(node.right);
if (node.left != null) st.push(node.left);
}
return res;
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> st = new Stack<>();
if (root == null) return res;
st.push(root);
while (!st.isEmpty()) {
TreeNode node = st.pop();
res.add(node.val);
if (node.left != null) st.push(node.left);
if (node.right != null) st.push(node.right);
}
Collections.reverse(res);
return res;
}
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> st = new Stack<>();
if (root == null) return res;
TreeNode node = root;
while (node != null || !st.isEmpty()) {
if (node != null) {
st.push(node);
node = node.left;
} else {
node = st.pop();
res.add(node.val);
node = node.right;
}
}
return res;
}
}
// 前序遍历:根左右
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stk = new LinkedList<TreeNode>();
while (root != null || !stk.isEmpty()) {
while (root != null) {
res.add(root.val);
stk.push(root);
root = root.left;
}
root = stk.pop();
root = root.right;
}
return res;
}
}
// 中序遍历:左根右
class Solution {
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;
}
}
// 后序遍历:左右根
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<Integer>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
result.addFirst(root.val);
root = root.right;
}
root = stack.pop();
root = root.left;
}
return result;
}
}
https://www.programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html