树的遍历有递归和非递归两种，LeetCode涉及的都是 iteration 方式。遍历基本上分成四种: preorder, postorder, inorder, level order (zigzag order 算是一个变体)。
就不说递归了，优点是实现简单，缺点是对与函数调用栈消耗较大，如果不是优化结果（with out memorization）会出现 overlapping problem 甚至导致 stack overflow.
用非递归方式实现树的遍历，有三种方法：
- 根据遍历的定义，如下面提到的 preorder traversal 的方法1
- 根据递归方式，用程序模拟函数调用栈的实现方式，如 preorder 方法1 和 inorder
- Morris Traversal，60/70年代Morris这位大神为了节省计算机资源发明的O(1) space complexity解法，有兴趣的可以看看
1和2都可以考虑，针对不同的遍历顺序，实现起来难易度不同
Note: All operations are based on the class:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}方法 1
public List<Integer> preorder(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
res.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return res;
}维护一个栈，先将根节点压栈，此后每次从栈中读取栈顶元素当做访问节点，分别将children按照先右后左的顺序压栈。
这个程序是根据前序遍历的定义解决的。我理解是因为这并不是一个DFS的solution (并没有做到 as deep as you can), 只是对访问顺序的模拟。
方法 2
- 深度优先 (DF): preorder, postorder, inorder -
stack
Depth First Traversal: go in subtree as deep as you can, backtrack. Differ on the order of visiting root, left, right subtrees.
public List<Integer> preorder(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.empty()) {
if (node != null) {
res.add(node.val);
stack.add(node);
node = node.left;
} else {
node = stack.pop();
node = node.right;
}
}
return res;
}
-
维护一个栈 s 和一个当前节点 n。初始时将 n 赋值为根节点。
-
逐个访问当前节点 n 的左子链上的节点，并推入栈中，直到没有左儿子。
-
取出栈顶的节点，将 n 赋值为该节点的右儿子。
-
不断执行 2，3，直到栈为空且当前节点也为空。
该方法模拟了递归的前序遍历中程序调用栈的行为过程：在调用栈中，会不断的递归进入左儿子链中，直到没有左儿子，再进入对右儿子的处理中。与递归方法的调用栈的不同之处在于，内层 while 循环将递归方法中针对左儿子链上所有节点的递归过程集中到了一起。
方法
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.empty()) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
node = stack.pop();
res.add(node.val);
node = node.right;
}
}
return res;
}
-
维护一个栈 s 和一个当前节点 n。初始时将 n 赋值为根节点。
-
将当前节点 n 的左子链上的节点逐个推入栈中，直到没有左儿子。
-
取出栈顶的节点，访问该节点，将 n 赋值为该节点的右儿子。
-
不断执行 2，3，直到栈为空且当前节点也为空。
跟前序遍历的方法二很类似。唯一的不同是访问当前节点的时机：前序遍历在入栈前访问，而中序遍历在出栈后访问。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<Integer>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode prev = root;
while (!stack.empty()) {
TreeNode node = stack.peek();
if ((node.left == null && node.right == null)
|| node.left == prev || node.right == prev) {
result.add(stack.pop().val);
prev = node;
continue;
}
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}根据后续遍历的定义，如果当前访问的不是叶子节点则继续向下层遍历。
- 广度优先 (BF): level order / zigzag order -
queue
Breadth First Traversal: visit each node, starting from the lowest level and moving down by level, visiting nodes from left to right.
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
int size = queue.size(); // record current level size
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
result.add(level);
}
Collections.reverse(result);
return result;
}
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Binary Tree Postorder Traversal
- Binary Tree Zigzag Level Order Traversal
- [Recover Binary Search Tree]
- Same Tree
- Balanced Tree
- Flatten Binary Tree to Linked List
- Symmetric Tree
- [Populating Next Right Pointers in Each Node II]
- Construct Binary Tree from Preorder and Inorder Traversal
- Construct Binary Tree from Inorder and Postorder Traversal
- [Unique Binary Search Trees]
- [Unique Binary Search Tress II]
- Validate Binary Search Tree
- Convert Sorted Array to Binary Search Tree
