二叉树的前序遍历
题目描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
思路
我们知道前序遍历是按照根-->左子树-->右子树的顺序来遍历的，如果要使用迭代的方法来解决，我们可以使用栈来解决，先把根节点放入栈中，然后将右孩子加入栈，再加入左孩子。因为这样子进栈后，出栈的顺序就是根-->左子树-->右子树
代码
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList();
Stack<TreeNode> stack=new Stack();
if(root==null){
return list;
}
//只要栈非空，则把栈顶元素弹出
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;
}
}二叉树的中序遍历
题目描述
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
思路
中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中）
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
代码
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 (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;
}
}二叉树的后序遍历
题目描述
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
提示：
树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100
思路
后续遍历的遍历顺序是左右根，前序遍历的遍历顺序是根左右，我们发现我们只需要调整一下左右孩子的进栈顺序，然后再反转一下，就可以得到后序遍历
代码
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList();
Stack<TreeNode> stack=new Stack();
if(root==null){
return list;
}
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
list.add(node.val);
if(node.left!=null){
stack.push(node.left);
}
if(node.right!=null){
stack.push(node.right);
}
}
//反转
Collections.reverse(list);
return list;
}
}二叉树的层序遍历
题目描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
前提知识
在解决这道题目之前，我们应该先了解什么是层序遍历
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。
队列先进先出，符合一层一层遍历的逻辑，我们可以使用队列来实现层序遍历
public void levelOrderTraversal(Node root){
if(root==null){
return;
}
Queue<Node> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
Node node=queue.poll();
System.out.print(node.val+" ");
if(node.left!=null) {
queue.offer(node.left);
}
if(node.right!=null) {
queue.offer(node.right);
}
}
}
代码
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null) {
return new ArrayList<List<Integer>>();
}
List<List<Integer>> res = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
//将根节点放入队列中，然后不断遍历队列
queue.add(root);
while(queue.size()>0) {
//获取当前队列的长度，这个长度相当于 当前这一层的节点个数
int size = queue.size();
ArrayList<Integer> tmp = new ArrayList<Integer>();
//将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
//如果节点的左/右子树不为空，也放入队列中
for(int i=0;i<size;++i) {
TreeNode t = queue.poll();
tmp.add(t.val);
if(t.left!=null) {
queue.offer(t.left);
}
if(t.right!=null) {
queue.offer(t.right);
}
}
//将临时list加入最终返回结果中
res.add(tmp);
}
return res;
}
}
