算法：二叉树遍历类题目
树的遍历顺序是依赖于 根 节点的位置，前序遍历的顺序为 根左右，中序遍历的顺序为 左根右，后序遍历的顺序为 左右根。除此以外还存在层次遍历。
在树类算法中，很多题目是基于树的遍历和树的性质而产生的，熟悉树的遍历和性质是灵活应用树类题目的前提。
那么什么是树和二叉树？
树（tree）是n（n>=0）个结点的有穷集。n=0时称为空树。在任意一个非空树中：（1）每个元素称为结点（node）；（2）仅有一个特定的结点被称为根结点或树根（root）。（3）当n>1时，其余结点可分为m（m≥0）个互不相交的集合T1，T2，……Tm，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作根的子树（subtree）。可见树（tree）的定义本身就是迭代递归的定义。
二叉树是树中节点的度不大于2的有序树，它是一种最简单且最重要的树。
1. 前根遍历
1.1 前根的递归遍历
由树的定义可知，树天生具有可迭代的特性。
// 由于方法中要方法结果列表，不可直接进行迭代，可以定义全局列表，或定义helper方法。
List<Integer> res = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return res;
}
// 先打印根节点，然后打印左子树，最后再打印右子树
res.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return res;
}
1.2 前根的迭代遍历
递归一般可以通过栈来进行描述，所以可以通过栈实现前根的迭代遍历。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.empty()) {
if (cur != null) {
res.add(cur.val);
stack.push(cur);
cur = cur.left;
} else {
TreeNode node = stack.pop();
if(node.right != null) {
cur = node.right;
}
}
}
return res;
}
这种方式是使用先遍历左子树，如果左子树为NULL, 则回退到存在的右节点，再遍历其左子树。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.add(root);
while(!stack.empty()) {
TreeNode node = stack.pop();
res.add(node.val);
// 先压入右节点，再压入左节点
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
stack.add(node.left);
}
}
return res;
}
也可以采用在压栈时，先压入右节点，再压入左节点。这样在弹出时可以按照先序遍历的顺序从左到右进行弹出。
2. 中根遍历
2.1 中根的递归遍历
// 由于方法中要方法结果列表，不可直接进行迭代，可以定义全局列表，或定义helper方法。
List<Integer> res = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return res;
}
inorderTraversal(root.left);
// 先打印根节点，然后打印左子树，最后再打印右子树
res.add(root.val);
inorderTraversal(root.right);
return res;
}
2.2 中根的迭代遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.empty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
TreeNode node = stack.pop();
res.add(node.val);
if(node.right != null) {
cur = node.right;
}
}
}
return res;
}
中根遍历可以先压左节点，再压右节点。再回退弹出时将其放入列表。
3. 后根遍历
3.1 后根的递归遍历
// 由于方法中要方法结果列表，不可直接进行迭代，可以定义全局列表，或定义helper方法。
List<Integer> res = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return res;
}
postorderTraversal(root.left);
postorderTraversal(root.right);
// 先打印根节点，然后打印左子树，最后再打印右子树
res.add(root.val);
return res;
}
3.2 后根的迭代遍历
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null) return res;
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
res.add(cur.val);
if(cur.left!=null) stack.push(cur.left);
if(cur.right!=null) stack.push(cur.right);
}
Collections.reverse(res);
return res;
}
可以采用先压左节点，再压右节点，最后再进行反转列表。另外如果使用的是LinkedList<>，则可以使用addFirst的方法。
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> res = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null) return res;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.addFirst(cur.val);
if(cur.left != null) stack.push(cur.left);
if(cur.right != null) stack.push(cur.right);
}
return res;
}
另外可以将每一个父节点后加一个NULL节点作为标识，在弹出时将其添加到结果List中。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.add(root);
while(!stack.empty()) {
TreeNode node = stack.pop();
if (node != null) {
// 将每一个父节点重新压入， 这里相当于进行了两遍的压栈
stack.push(node);
stack.push(null);
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
stack.add(node.left);
}
} else {
// 将父节点进行添加
TreeNode r = stack.pop();
res.add(r.val);
}
}
return res;
}
4. 层次遍历
4.1 基于递归的层次遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
levelHelper(res, root, 0);
return res;
}
private void levelHelper(List<List<Integer>> res, TreeNode root, int level) {
if (root == null)
return;
// level表示的是层数，如果level >= list.size()，说明到下一层了，所以
// 要先把下一层的list初始化，防止下面add的时候出现空指针异常
if (level >= res.size()) {
res.add(new ArrayList<>());
}
// level表示的是第几层，这里访问到第几层，我们就把数据加入到第几层
res.get(level).add(root.val);
// 当前节点访问完之后，再使用递归的方式分别访问当前节点的左右子节点
levelHelper(res, root.left, level + 1);
levelHelper(res, root.right, level + 1);
}
传入参数为结果list, 遍历节点root, 和遍历的层数level。如果level大于等于res列表中的。
4.2 基于迭代的层次遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
for (int i=0;i < size; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
result.add(list);
}
return result;
}
使用queue的先进先出的性质，进行层次遍历。
基于树的递归应用问题
由树的定义可知，树的定义是递归的，所以可以通过递归去解决一些类树的问题。使用递归解决问题一般有两种思路：1. 自顶向下。2. 自底向上。
- 自顶向下意味着在每一个递归层级，先方法当前节点应用计算一些值。
- 自底向上意味着先进行递归遍历，利用递归的回溯的原理，在递归的回溯过程中应用计算。
- 二叉树的最大深度
自顶向下：
int maxDepth = 0;
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
callDepth(root, 1);
return maxDepth;
}
private void callDepth(TreeNode root, int level) {
// 处理特殊null节点，返回特定值。
if (root == null) {
return;
}
// 如果当前节点满足条件，更新结果值
if (root.left == null && root.right == null) {
maxDepth = Math.max(maxDepth, level);
}
// 左右子树进行递归
callDepth(root.left, level + 1);
callDepth(root.right, level + 1);
}
自底向上：
public int maxDepth(TreeNode root) {
// 处理特殊的null节点，返回特定值
if (root == null) {
return 0;
}
// 处理特定值作为递归出口值
if (root.left == null && root.right == null) {
return 1;
}
// 左右子树进行递归
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
- 对称的二叉树
自顶向下：
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return false;
}
return isSymmetricCore(root.left, root.right);
}
private boolean isSymmetricCore(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
return isSymmetricCore(left.left, right.right) && isSymmetricCore(left.right, right.left);
}
- 路径总和
自低向上
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return targetSum == root.val;
}
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
}
- 由中序和后序遍历构造二叉树
自顶向下：
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (postorder.length == 0) {
return null;
}
int len = postorder.length;
return buildTreeCore(inorder, 0, len - 1, postorder, 0, len - 1);
}
private TreeNode buildTreeCore(int[] inorder, int s1, int e1, int[] postorder, int s2, int e2) {
if (s2 > e2) {
return null;
}
int rootVal = postorder[e2];
TreeNode root = new TreeNode(rootVal);
// 算出当前根节点到s1的距离
int mid = 0;
while (inorder[s1 + mid] != rootVal) mid++;
root.left = buildTreeCore(inorder, s1, s1 + mid - 1, postorder, s2, s2 + mid - 1);
root.right = buildTreeCore(inorder, s1 + mid + 1, e1, postorder, s2 + mid, e2 - 1);
return root;
}
- 由前序和中序遍历生成二叉树
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) {
return null;
}
int len = preorder.length;
return buildTreeCore(preorder, 0, len - 1, inorder, 0, len - 1);
}
private TreeNode buildTreeCore(int[] preorder, int s1, int e1, int[] inorder, int s2, int e2) {
if (s1 > e1) {
return null;
}
int rootVal = preorder[s1];
TreeNode root = new TreeNode(rootVal);
if (s1 == e1) {
return root;
}
// 算出当前根节点到s1的距离
int mid = 0;
while (inorder[s2 + mid] != rootVal) mid++;
root.left = buildTreeCore(preorder, s1 + 1, s1 + mid, inorder, s2 , s2 + mid -1);
root.right = buildTreeCore(preorder, s1 + mid + 1, e1, inorder, s2 + mid + 1, e2);
return root;
}
由上面的题目可以看出，大部分的算法题目都可以通过这两种方法实现。但是两种方式并不能适应于所有的题目。如果题目可以在当前的任意节点就可以判断出返回的结果，则适合使用自顶向下（增加剪枝效果）。如果题目必须遍历到叶子节点后才能计算出中间值，则需要使用自底向上。当然如果是根据叶子节点的值的状态，或者在遍历过程中并不需要更新结果值，那么这两种方式其实是很混淆的。
基于树的迭代应用问题
基于迭代进行处理，一般围绕层次遍历，先序，后序遍历或中序的迭代遍历进行展开的。
- 二叉树的最大深度
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int count = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size -- > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
count ++;
}
return maxDepth;
}
使用层次遍历的方式实现获取二叉树的深度的算法。
- 镜像二叉树
public boolean isSymmetric2(TreeNode root) {
if (root == null) {
return false;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root.left);
queue.add(root.right);
while (!queue.isEmpty()) {
TreeNode left = queue.poll();
TreeNode right = queue.poll();
if (left == null && right == null) {
continue;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
queue.add(left.left);
queue.add(right.right);
queue.add(left.right);
queue.add(right.left);
}
return false;
}
只判断为false的情况，为true的情况下进行跳过。
- 路径总和
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
if (node.left == null && node.right == null) {
if (targetSum == node.val) return true;
}
if (node.left != null) {
node.left.val = node.left.val + node.val;
stack.push(node.left);
}
if (node.right != null) {
node.right.val = node.right.val + node.val;
stack.push(node.right);
}
}
return false;
}
由于只使用一次，所以可以使用TreeNode 的val作为临时存储值的地方。
