三序遍历
递归
迭代
Parent
复杂度
Binary Tree Preorder Traversal
preorder 直接用 stack; 边弹边压
inorder 用 stack + cur; 压到底后再弹
postorder 用 stack + cur + prev;
迭代就是用stack, 先push(root), 再用while loop不断pop, 因为栈先入后出的特点, push的时候先push右边的,再左边的.
带parent的写法, 有些tricky.
以 cur != null 为 while 循环条件；
直接输出 cur.val
cur 左面有东西就 cur = cur.left;
左面没有但右面有，cur = cur.right;
其他情况就属于要往上回溯了，注意这个回溯长度可以是任意的，我们要注意把 cur 放到正确的位置上。(长度是任意的, 重点)
我们要找的位置相对于从左往上的路线而言，是 cur 往上看第一个右节点不为 null 的地方；相对于从右往上的路线而言就是无脑往上走直到走向成从左往上为止。(重点)
在任何时刻追溯完毕发现 cur.parent 为空，说明走完了。(重点)
否则 cur 就是 cur.parent.right.(重点)
public static void printPreorder(TreeNode root) {
TreeNode cur = root;
while(cur != null){
System.out.println(cur.val);
if(cur.left != null){
cur = cur.left;
} else if(cur.right != null){
cur = cur.right;
} else {
while(cur.parent != null && (cur.parent.right == null || cur == cur.parent.right)){
cur = cur.parent;
}
if(cur.parent == null) break;
cur = cur.parent.right;
}
}
}
Binary Tree Inorder Traversal
preorder 直接用 stack; 边弹边压
inorder 用 stack + cur; 压到底后再弹
postorder 用 stack + cur + prev;
递归 ✓
迭代 ✓
parent
复杂度 ✓
迭代: stack 写法要记住的细节是，两个 while 循环里都是 cur != null
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
list.add(node.val);
cur = node.right;
}
return list;
}
}
利用外层循环, 取消内层循环
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if(root==null) return list;
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<TreeNode>();
while(!stack.isEmpty() || cur!=null){
if(cur!=null){
stack.push(cur);
cur = cur.right;
}
else{
cur = stack.pop();
list.add(cur.val);
cur = cur.left;
}
}
return root;
}
}
Parent: In-order 的 parent 指针写法稍微 tricky 一些，考虑到 in-order 的特性和面经问到的内容，我写了两个函数，主要是 getSuccessor()，然后把 root 放到二叉树最左面为起点依次调用。+
getSuccessor() 流程，其实有点像 morris - traversal:
如果 cur 右子树不为空，返回右子树里面最左面的点(也即 cur.right 一路向左最远的点)
否则一路沿着(右child - parent) 的路线往上走，然后返回 parent 就行了
public static void printInorder(TreeNode root) {
TreeNode cur = root;
while(cur.left != null){
cur = cur.left;
}
// Now current is at left most pos
while(cur != null){
System.out.println(cur.val);
cur = getSuccessor(cur);
}
}
private static TreeNode getSuccessor(TreeNode cur){
// Find leftmost node in right subtree
if(cur.right != null){
cur = cur.right;
while(cur.left != null) cur = cur.left;
} else {
//
while(cur.parent != null && cur == cur.parent.right){
cur = cur.parent;
}
if(cur.parent == null) return null;
cur = cur.parent;
}
return cur;
}
Inorder Successor in BST
BST 里面，任意位置，任意楼层，都可以通过 value 的比较确定相对位置，这是 BST 一个最好用的性质。
自己写的时候开始想错了, 用stack存了访问过的点, 然后找第一个stack的右子数最左节点. 实际上只要保存一个大于value的点即可, 如果找到了, 向左走, 看能否找到更小的; 没找到向右走, 搜索可能大于value的点.
public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode rst = null;
while(root != null){
if(root.val > p.val){
rst = root;
root = root.left;
} else {
root = root.right;
}
}
return rst;
}
}
顺着这个思路讲，BST 里面找 in-order predecessor 也特简单，这次往左走的时候不记，往右走的时候记，就行了。
public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode rst = null;
while(root != null){
if(root.val > p.val){
root = root.left;
} else {
rst = root;
root = root.right;
}
}
return rst;
}
}
Binary Tree Postorder Traversal
第一个地方是 post order 因为每一步用 stack 顶元素作为新的 cur，在 while 循环中只需要以 !stack.isEmpty() 为条件去判断。
post order 遍历中最重要的是 prev 与 cur 的相对关系，相当于存了上一步的动作，用作下一步的方向。
用一个 stack 存着所有的 candidate node，栈顶为当前 candidate，并且以栈是否为空做唯一判断标准（还有没有要看的 candidate）
复习的时候写错了, 应该严格按照逻辑,
每次iterate开始的时候, cur是栈顶的元素, 每次iterate结束的时候, prev=cur; 在 while 循环中只需要以 !stack.isEmpty() 为条件去判断。
当cur在prev下面的时候, 如果cur左边有节点,压入cur.left, 如果cur.right存在, 压入cur.right;
当cur.left==prev时, 通过方向知道回溯已经开始了, 左边已经处理完,该处理右边, 此时如果cur.right存在则压入.
剩余情况就是左边和右边都处理完了, 处理当前的元素, pop栈顶元素
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { Stack<TreeNode> stack = new Stack<TreeNode>(); List<Integer> list = new ArrayList<Integer>(); if(root==null) return list; stack.push(root); TreeNode cur = root; TreeNode prev = null; while(!stack.isEmpty()){ cur = stack.peek(); // cur 在 prev 下面，要尝试探索所有 cur 下面的节点 // 如果 cur 是叶节点的话，会在最后把 prev 赋值成 cur，再下一轮的时候被 pop 掉。 if(prev==null||prev.left==cur||prev.right == cur){ if(cur.left!=null) stack.push(cur.left); else if(cur.right!=null) stack.push(cur.right); } // 刚把左边处理完回来，看看右边还有没有节点 else if(cur.left==prev){ if(cur.right!=null) stack.push(cur.right); } // 左右子树都处理完了，处理当前节点。 else{ list.add(cur.val); stack.pop(); } prev = cur; } return list; } }
还有一种写法是利用后序遍历的特性, 先序遍历是root,左, 右; 后序遍历是左,右, root, 即root, 右, 左的逆序. 利用先序的code, 先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;
}
模板化写法
PreOrder
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;
}
Inorder
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
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;
}
Binary Tree Vertical Order Traversal
BFS, 用两个queue,一个存当前层数的节点, 一个存vertical order. 用map记录访问过得点
记得maintain两个值, min和max, 最后搜索的时候好用
public class Solution { public List<List<Integer>> verticalOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); Queue<Integer> level = new LinkedList<Integer>(); queue.offer(root);level.offer(0); int minodr = Integer.MAX_VALUE; int maxodr = Integer.MIN_VALUE; while(!queue.isEmpty()){ TreeNode cur = queue.poll(); int order = level.poll(); minodr = Math.min(minodr, order);//key point maxodr = Math.max(maxodr, order);//key point if(!map.containsKey(order)) map.put(order, new ArrayList<Integer>()); map.get(order).add(cur.val); if(cur.left!=null){ queue.offer(cur.left); level.offer(order-1); } if(cur.right!=null){ queue.offer(cur.right); level.offer(order+1); } } List<List<Integer>> ans = new ArrayList<List<Integer>>(); for(int i=minodr; i<=maxodr; i++){ if(map.containsKey(i)) ans.add(map.get(i)); } return ans; } }