Tree
- Traversal(遍历)
-
- 基本遍历类型
-
- 1. Inorder(中序)
-
- (1) 递归
- (2) 使用栈迭代
- (3) Morris遍历(虚拟节点)
- 2. Preorder( 前序)
-
- (1)递归
- (2)使用栈迭代
- (3)Morris遍历
- 3. Postorder( 后序)
-
- (1) 递归
- (2) 使用栈迭代
- (3) Morris遍历
- 4. Iterator( 迭代器)
- 5. 类似题目
Traversal(遍历)
基本遍历类型
1. Inorder(中序)
94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes’ values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
(1) 递归
TC: O(n) SC: O(n)
public static void inOrder(Node root) {
if (root == null) return;
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
(2) 使用栈迭代
解题思路
使用栈以及一个遍历指针
TC: O(n) SC: O(n)
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> stk = new ArrayDeque<>();
TreeNode p = root;
while(p != null || !stk.isEmpty()){
if (p != null){
stk.push(p);
p = p.left;
}else if (!stk.isEmpty()){
TreeNode cur = stk.pop();
res.add(cur.val);
p = cur.right;
}
}
return res;
}
(3) Morris遍历(虚拟节点)
解题思路
一般面试考遍历考递归或者迭代的算法比较常见，morris遍历比较难，如果想提高印象分可以使用，我会在另一篇博客中详细说明这个算法
TC: O(n) SC: O(1)
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
TreeNode p1 = root;
TreeNode p2 = null;
while(p1 != null){
p2 = p1.left;
if (p2 != null){
while(p2.right != null && p2.right != p1){
p2 = p2.right;
}
if (p2.right == p1){
p2.right = null;
}else{
p2.right = p1;
p1 = p1.left;
continue;
}
}
res.add(p1.val);
p1 = p1.right;
}
return res;
}
2. Preorder( 前序)
Tree: Preorder Traversal
Complete the preOrder function in your editor below, which has parameter: a pointer to the root of a binary tree. It must print the values in the tree’s preorder traversal as a single line of space-separated values.
Input Format
Our hidden tester code passes the root node of a binary tree to your preOrder function.
Constraints
Nodes in the tree
Output Format
Print the tree’s preorder traversal as a single line of space-separated values.
Sample Input
1
\
2
\
5
/ \
3 6
\
4
Sample Output
1 2 5 3 4 6
(1)递归
TC:O(n) SC: O(n)
public static void preOrder(Node root) {
if (root == null) return;
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
(2)使用栈迭代
TC:O(n) SC: O(n)
解题思路
每个节点出栈即打印，子节点从右往左压栈
public static void preOrder(Node root) {
Deque<Node> stk = new ArrayDeque<>();
stk.push(root);
while(!stk.isEmpty()){
Node cur = stk.pop();
System.out.print(cur.data + " " );
if (cur.right != null) stk.push(cur.right);
if (cur.left != null) stk.push(cur.left);
}
}
(3)Morris遍历
TC:O(n) SC: O(1)
解题思路
和中序遍历相比，如果改节点不存在左孩子则直接打印当前节点
public static void preOrder(Node root) {
if (root == null)return;
Node p1 = root;
Node p2 = null;
while(p1 != null){
p2 = p1.left;
if(p2 != null){
while(p2.right != null && p2.right != p1){
p2 = p2.right;
}
if (p2.right == p1){
p2.right = null;
}else{
System.out.print(p1.data + " ");
p2.right = p1;
p1 = p1.left;
continue;
}
}else{
System.out.print(p1.data + " ");
}
p1 = p1.right;
}
}
3. Postorder( 后序)
Tree: Postorder Traversal
Complete the postOrder function in your editor below, which has parameter: a pointer to the root of a binary tree. It must print the values in the tree’s postorder traversal as a single line of space-separated values.
Input Format
Our hidden tester code passes the root node of a binary tree to your postOrder function.
Constraints
1 Nodes in the tree 500
Output Format
Print the tree’s postorder traversal as a single line of space-separated values.
Sample Input
1
\
2
\
5
/ \
3 6
\
4
Sample Output
4 3 6 5 2 1
(1) 递归
TC:O(n) SC: O(n)
public static void postOrder(Node root) {
if (root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
(2) 使用栈迭代
第一种比较hacky的方式就是利用list的addFirst这个性质。许多转换遍历顺序的题目可以用这个方法修改输出。但是实际遍历并不是符合题目要求的，有比较较真的面试官会要求实现完全符合遍历要求的算法。
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return ans;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
ans.addFirst(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
return ans;
}
这种算法就是完全符合后序遍历，但是也有需要注意的一点，就是如果将指针节点设置为null，那么当出现子节点的父节点没有右边节点时会fail第一个if statement，而这个子节点永远不会入栈。所以指针节点p必须确保初始的时候不与树中任何的节点相等。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> stk = new ArrayDeque<>();
stk.push(root);
TreeNode p = new TreeNode(-9999999);
while(!stk.isEmpty()){
TreeNode peak = stk.peek();
if (peak.left != null && p != peak.left && p != peak.right){
stk.push(peak.left);
}else if (peak.right != null && p != peak.right){
stk.push(peak.right);
}else{
res.add(stk.pop().val);
p = peak;
}
}
return res;
}
(3) Morris遍历
解题思路
依次逆序打印右子树的边
TC:O(n) SC: O(1)
public static void postOrder(Node root) {
if (root == null)return;
Node p1 = root;
Node p2 = null;
while(p1 != null){
p2 = p1.left;
if(p2 != null){
while(p2.right != null && p2.right != p1){
p2 = p2.right;
}
if (p2.right == p1){
p2.right = null;
printEdge(p1.left);
}else{
p2.right = p1;
p1 = p1.left;
continue;
}
}
p1 = p1.right;
}
printEdge(root);
}
private static void printEdge(Node root){
Node tail = reverse(root);
Node cur = tail;
while(cur != null){
System.out.print(cur.data + " ");
cur = cur.right;
}
reverse(tail);
}
private static Node reverse(Node root){
Node pre = null;
Node cur = root;
while(cur != null){
Node next = cur.right;
cur.right = pre;
pre = cur;
cur = next;
}
return pre;
}
4. Iterator( 迭代器)
173. Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Example:
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // return 3
iterator.next(); // return 7
iterator.hasNext(); // return true
iterator.next(); // return 9
iterator.hasNext(); // return true
iterator.next(); // return 15
iterator.hasNext(); // return true
iterator.next(); // return 20
iterator.hasNext(); // return false
Note:
next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.
其实就是把中序遍历包了一层迭代器的皮，需要把初始压栈和遍历节点分成两个部分，符合迭代器的规范就行。
class BSTIterator {
Deque<TreeNode> stk;
TreeNode p;
public BSTIterator(TreeNode root) {
stk = new ArrayDeque<TreeNode>();
p = root;
while(p != null){
stk.push(p);
p = p.left;
}
}
/** @return the next smallest number */
public int next() {
int res = 0;
if (hasNext()){
TreeNode cur = stk.pop();
res = cur.val;
cur = cur.right;
while(cur != null){
stk.push(cur);
cur = cur.left;
}
}
return res;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stk.isEmpty();
}
}
5. 类似题目
589. N-ary Tree Preorder Traversal
590. N-ary Tree Postorder Traversal
这个就是非常直观的binary tree traversal的扩展，不同之处仅仅在于左右子节点变成了一个子节点的list。
![Java 八种排序算法总结[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)