二叉树遍历

二叉树的遍历有四种方式，前序，中序，后序，层序，大多数树相关的算法题都可以通过树的遍历得到解决

1. 前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 根节点-左子节点-右子节点
public void preOrderTraversal(TreeNode root) {
  	if (root == null) {
    		return;
  	}
  	System.out.print(root.val + " ");
  	preOrderTraversal(root.left);
  	preOrderTraversal(root.right);
}

// 先访问根节点，右子节点需要入栈，便于回溯
public void preOrderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    while(!stack.isEmpty() || root != null) {
        if (root != null) {
            System.out.print(root.val + " ");
            stack.push(root.right);
            root = root.left;
        } else {
            root = stack.pop();
        }
    }
}

2. 中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//左节点-根节点-右节点
public void inOrderTraversal(TreeNode root) {
  if (root == null) {
    return;
  }
  inOrderTraversal(root.left);
  System.out.print(root.val + " ");
  inOrderTraversal(root.right);
}

// 先遍历左节点，根节点需要入栈方便回溯
public void inOrderTraversal(TreeNode root) {
  Stack<TreeNode> stack = new Stack<TreeNode>();
  while (!stack.isEmpty() || root != null) {
    if (root != null) {
      stack.push(root);
      root = root.left;
    } else{
      root = stack.pop();
      System.out.print(root.val + " ");
      root = root.right;
    }
  }
}

3. 后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//左子节点-右子节点-根节点
public void postOrderTraversal(TreeNode root) {
  if (root == null) {
    return;
  }
  postOrderTraversal(root.left);
  postOrderTraversal(root.right);
  System.out.print(root.val + " ");
}

//后续遍历的结果reverse即为根节点-左子节点-右子节点遍历结果，可以转化为类似前序遍历方式
public void postOrderTraversal(TreeNode root) {
  Stack<TreeNode> stackTmp = new Stack<TreeNode>();
  Stack<TreeNode> ret = new Stack<TreeNode>();
  while(!stackTmp.isEmpty() || root != null) {
    if (root != null) {
      ret.add(root);
      stackTmp.add(root.left);
      root = root.right;
    } else {
      root = stackTmp.pop();
    }
  }
  while(!ret.isEmpty()) {
    System.out.print(ret.pop().val + " ");
  }
}

4. 层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void layerTraversal(TreeNode root) {
  if (root == null) {
    return;
  }
  Queue<TreeNode> queue = new LinkedList<TreeNode>();
  queue.offer(root);
  while ( !queue.isEmpty()) {
    root = queue.poll();
    System.out.print(root.val + " ");
    if (root.left != null) {
      queue.offer(root.left);
    }
    if (root.right != null) {
      queue.offer(root.right);
    }
  }
}

5. z形遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//层序遍历，隔层reverse，双重循环，外重循环遍历层数，内层循环遍历当前层
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
  ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
  if (root == null) {
    return ret;
  }
  Queue<TreeNode> tree = new LinkedList<>();
  tree.offer(root);
  boolean leftToRight = true;
  while (!tree.isEmpty()) {
    int layerSize = tree.size();
    ArrayList<Integer> layer = new ArrayList<>();
    while (layerSize-- > 0) {
      root = tree.poll();
      layer.add(root.val);
      if (root.left != null) {
        tree.offer(root.left);
      }
      if (root.right != null) {
        tree.offer(root.right);
      }
    }
    if (!leftToRight){
      Collections.reverse(layer);
    }
    leftToRight = !leftToRight;
    ret.add(layer);
  }
  return ret;
}

LeetCode树相关算法题

题目 解决方案 代码
Minimum Depth of Binary Tree 层序遍历 Minimum Depth of Binary Tree
sum-root-to-leaf-numbers 前序遍历 sum-root-to-leaf-numbers
binary-tree-maximum-path-sum 后序遍历，子问题化简 binary-tree-maximum-path-sum
populating-next-right-pointers-in-each-node 层序遍历，完美二叉树，利用指向右节点的引用遍历当前层 populating-next-right-pointers-in-each-node-ii
populating-next-right-pointers-in-each-node-ii 层序遍历，找到当前层的第一个节点 populating-next-right-pointers-in-each-node-ii
path-sum 前序遍历，累加路径值 path-sum
path-sum-ii 前序遍历，累加路径值 path-sum-ii
balanced-binary-tree 后序遍历，递归求树深 balanced-binary-tree
construct-binary-tree-from-inorder-and-postorder-traversal 后续遍历的最后一个节点是根节点，中序遍历中根节点左边的是左子树，右边的是右子树 construct-binary-tree-from-inorder-and-postorder-traversal
construct-binary-tree-from-preorder-and-inorder-traversal 前序遍历的第一个节点是根节点，中序遍历中根节点左边的是左子树，右边的是右子树 construct-binary-tree-from-preorder-and-inorder-traversal
maximum-depth-of-binary-tree 后续遍历，累计求值 maximum-depth-of-binary-tree
symmetric-tree 左右子树遍历方向相反，逐个比较 symmetric-tree
same-tree 两个树用相同的方式遍历，比如前序遍历 IsSameTree
recover-binary-search-tree 搜索树中序遍历有序，按中序遍历查找错误点 RecoverTree
unique-binary-search-trees-ii 搜索树中序遍历有序，中序遍历必须升序 IsValidBST
unique-binary-search-trees 动态规划，划分左右子树，数种类=左子树种类*右子树种类 NumBST

剑指offer树相关题目（distinct with leetcode）

题目 解决方案 代码
树的子结构 前序遍历，子问题化简 IsSubTree
二叉树的镜像 前序遍历，子问题化简 MirrorTree
二叉搜索树的后序遍历序列 子问题化简 判断后序是否是搜索二叉树
二叉搜索树与双向链表 中序遍历，子问题化简 二叉搜索树转换成排序的双向链表
二叉树的下一个结点 分情况讨论 二叉树的下一个节点
二叉搜索树的第k个结点 中序遍历有序，遍历过程计数 二叉搜索树的第k小节点