창고는 두 갈래 나무가 반복적으로 흐르도록 실현한다
17412 단어 일반 알고리즘
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
if(cur != null){
// , , ,
// ,
stack.push(cur);
//cur , , ( )
stack.push(null);
// , cur,left,righ
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
}else{
res.add(stack.pop().val);
}
}
return res;
}
일반 교체
//
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) return res;
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
res.add(cur.val);
stack.push(cur.right);
cur = cur.left;
} else cur = stack.pop();
}
return res;
}
//
public List<Integer> inorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
List<Integer> list = new LinkedList<>();
if (root == null) return list;
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> postorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root, pre = null;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.peek();
//
if (cur.right == null || cur.right == pre) {
res.add(cur.val);
stack.pop();
pre = cur;
cur = null;
} else cur = cur.right;
}
}
return res;
}