⼆叉树遍历模板（前序，中序，后序）Pre Order Traverse
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.add(p.val);  // Add before going to children
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
}
In Order Traverse
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
先序中序后序遍历二叉树Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode node = stack.pop();
result.add(node.val);  // Add after all left children
p = node.right;
}
}
return result;
}
Post Order Traverse
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.addFirst(p.val);  // Reverse the process of preorder            p = p.right;            // Reverse the process of preorder
} else {
TreeNode node = stack.pop();
p = node.left;          // Reverse the process of preorder        }
}
return result;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。