Given a binary tree, return the preorder traversal of its nodes' values.
For example: Given binary tree {1,#,2,3},
1 / 2 / 3
return [1,2,3].
时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间 对于二叉树b=2
用迭代法做深度优先搜索的技巧就是使用一个显式声明的Stack存储遍历到节点,替代递归中的进程栈,实际上空间复杂度还是一样的。对于先序遍历,我们pop出栈顶节点,记录它的值,然后将它的左右子节点push入栈,以此类推。
public class Solution { public List<Integer> preorderTraversal(TreeNode root) { Stack<TreeNode> s = new Stack<TreeNode>(); List<Integer> res = new LinkedList<Integer>(); if(root!=null) s.push(root); while(!s.isEmpty()){ TreeNode curr = s.pop(); res.add(curr.val); if(curr.right!=null) s.push(curr.right); if(curr.left!=null) s.push(curr.left); } return res; } }
Given a binary tree, return the inorder traversal of its nodes' values.
For example: Given binary tree {1,#,2,3},
1 / 2 / 3
return [1,3,2].
时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间 对于二叉树b=2
用栈中序遍历没有先序遍历那么直观,因为我们不能马上pop出当前元素,而要先把它的左子树都遍历完才能pop它自己。所有我们先将将最左边的所有节点都push进栈,然后再依次pop并记录值,每pop一个元素后再看它有没有右子树,如果右的话,我们再将它的右节点和右子树中最左边的节点都push进栈,再依次pop。
public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new LinkedList<Integer>(); Stack<TreeNode> s = new Stack<TreeNode>(); //先将最左边的节点都push进栈 if(root!=null){ pushAllTheLeft(s, root); } while(!s.isEmpty()){ TreeNode curr = s.pop(); res.add(curr.val); //如果有右子树,将右节点和右子树的最左边的节点都push进栈 if(curr.right != null){ pushAllTheLeft(s, curr.right); } } return res; } private void pushAllTheLeft(Stack<TreeNode> s, TreeNode root){ s.push(root); while(root.left!=null){ root = root.left; s.push(root); } } }
Given a binary tree, return the postorder traversal of its nodes' values.
For example: Given binary tree {1,#,2,3},
1 / 2 / 3
return [3,2,1].
时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间 对于二叉树b=2
后序遍历就不能简单的改变pop顺序来实现了,我们知道根节点(这里的根节点不是整个树的根,而是相对于左右节点的跟)是在左右节点都计算完才计算的,所以我们会遇到两次根节点,第一次遇到根节点时我们将左右节点加入栈,但不把根节点pop出去,等到处理完左右节点后,我们又会遇到一次根节点,这时再计算根节点并把它pop出去。为了判断是第一次还是第二次遇到这个根节点,我们可以用一个数据结构把这个信息封装进去,第一次遇到的时候将其设为已经访问了一次,这样第二次遇到时发现已经访问了一次,就可以直接pop了。
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { Stack<PowerNode> s = new Stack<PowerNode>(); List<Integer> res = new LinkedList<Integer>(); if(root!=null) s.push(new PowerNode(root, false)); while(!s.isEmpty()){ PowerNode curr = s.peek(); //如果是第二次访问,就计算并pop该节点 if(curr.visited){ res.add(curr.node.val); s.pop(); } else { //如果是第一次访问,就将它的左右节点加入stack,并设置其已经访问了一次 if(curr.node.right!=null) s.push(new PowerNode(curr.node.right, false)); if(curr.node.left!=null) s.push(new PowerNode(curr.node.left, false)); curr.visited = true; } } return res; } private class PowerNode { TreeNode node; boolean visited; public PowerNode(TreeNode n, boolean v){ this.node = n; this.visited = v; } } }
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example: Given binary tree {3,9,20,#,#,15,7},
3 / / 9 20 / / 15 7
return its bottom-up level order traversal as: (II)
[ [15,7], [9,20], [3] ]
return its level order traversal as: (I)
[ [3], [9,20], [15,7] ]
时间 O(b^(h+1)-1) 空间 O(b^h)
本题实质是广度优先搜索BFS,而用队列可以轻松的以迭代形式实现它。不过不同于BFS的是,层序遍历需要在队列中记住每一层的分割点,而BFS不关心层数只要遍历到指定元素就行了。为了记住这个分割点,我们在进入下一层之前先记下这一层的元素个数N(其实就是当前queue的大小),然后只遍历N个节点(展开下一层节点的同时queue中会新加入很多下下一层的节点)。遍历完N个节点后记录新的层数,再进入下一层。对于II,返回的层是逆序的,我们只要在结果中,每次把下面新一层加到当前这层的前面就行了
public class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<List<Integer>>(); Queue<TreeNode> q = new LinkedList<TreeNode>(); if(root != null) q.offer(root); while(!q.isEmpty()){ int size = q.size(); List<Integer> level = new LinkedList<Integer>(); //控制当前层的遍历次数 for(int i =0; i < size; i++){ TreeNode curr = q.poll(); level.add(curr.val); if(curr.left!=null) q.offer(curr.left); if(curr.right!=null) q.offer(curr.right); } res.add(level); //对于II, 我们要逆序加入 //res.add(0, level) } return res; } }
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example: Given binary tree {3,9,20,#,#,15,7},
3 / / 9 20 / / 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
时间 O(b^(h+1)-1) 空间 O(b^h)
ZigZag遍历时,奇数层正序记录,偶数层逆序记录。可以通过结果中已有的层数来判断。
public class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<List<Integer>>(); Queue<TreeNode> q = new LinkedList<TreeNode>(); if(root != null) q.offer(root); while(!q.isEmpty()){ int size = q.size(); List<Integer> level = new LinkedList<Integer>(); for(int i =0; i < size; i++){ TreeNode curr = q.poll(); //根据结果中已有的层数控制正序还是逆序 if(res.size() % 2 == 0){ level.add(curr.val); } else { level.add(0,curr.val); } if(curr.left!=null) q.offer(curr.left); if(curr.right!=null) q.offer(curr.right); } res.add(level); } return res; } }