树专题 —— 二叉树前序遍历
大家好，我是 方圆。本篇关于二叉树的前序遍历，主要由题目进行展开，如果大家想要找刷题路线的话，可以参考 Github: LeetCode。
前序遍历
前序遍历对节点的操作顺序是 “根左右”，遍历每个节点时，会 先对每个节点进行操作，再去遍历其他节点，一般使用前序遍历解决的问题具有 “先处理当前节点，再去处理左右子树” 的特点模板如下：
private void preorder(TreeNode root) {
if (root == null) {
return;
}
// do something...
preorder(root.left);
preorder(root.right);
}
我们先来看几道简单的题目：
根据题意，我们需要先将当前节点的左右子树交换再去处理左右子树节点，题解如下：
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
根据题意，如果其中一棵树的节点为空那么该位置的节点为另一棵树的节点，否则我们将两节点值相加创建新的节点。因为创建新的节点 需要改变节点间的引用关系，所以需要利用递归方法的返回值：
TreeNode root = new TreeNode(root1.val + root2.val);
root.left = mergeTrees(root1.left, root2.left);
root.right = mergeTrees(root1.right, root2.right);
完整的题解如下，对两棵树同时进行前序遍历即可：
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
TreeNode root = new TreeNode(root1.val + root2.val);
root.left = mergeTrees(root1.left, root2.left);
root.right = mergeTrees(root1.right, root2.right);
return root;
}
二叉树对称需要保证对称轴两侧“对应位置的节点相同”，镜面对称需要分别比较对称轴左侧的左子树和对称轴右侧的右子树以及对称轴左侧的右子树和对称轴右侧的左子树，比较完当前节点之后，再去比较当前节点的左右子树，前序遍历二叉树即可，题解如下：
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return doIsSymmetric(root.left, root.right);
}
private boolean doIsSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
boolean flag1 = doIsSymmetric(left.left, right.right);
boolean flag2 = doIsSymmetric(left.right, right.left);
return flag1 && flag2;
}
本题是根据二叉搜索树的性质来创建一棵二叉搜索树，每次我们取中点值为当前节点值，中点左侧的值为左子树，中点右侧的值为右子树，创建当前节点后，再去创建它的左右子树，前序遍历建树即可，题解如下：
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + right >> 1;
TreeNode node = new TreeNode(nums[mid]);
node.left = build(nums, left, mid - 1);
node.right = build(nums, mid + 1, right);
return node;
}
}
相关练习
接下来我们看一些中等难度的题目，来加深对前序遍历的理解：
我们可以通过每次取区间最大值创建当前节点，使用最大值索引将区间分为左子树区间和右子树区间，再根据两区间分别创建当前节点的左右子树，前序遍历执行该逻辑即可，题解如下：
public TreeNode constructMaximumBinaryTree(int[] nums) {
return doConstructMaximumBinaryTree(nums, 0, nums.length - 1);
}
private TreeNode doConstructMaximumBinaryTree(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int max = left;
for (int i = left; i <= right; i++) {
if (nums[i] > nums[max]) {
max = i;
}
}
TreeNode node = new TreeNode(nums[max]);
node.left = doConstructMaximumBinaryTree(nums, left, max - 1);
node.right = doConstructMaximumBinaryTree(nums, max + 1, right);
return node;
}
二叉搜索树的序列化和反序列化可以通过两次前序遍历来实现，序列化时前序遍历的节点值排列顺序为“根左右”，反序列化时根据“根左右”的顺序每次拿出“根节点”拼接在当前位置，再根据二叉搜索树的性质：根节点大于左子树任意节点，根节点小于右子树任意节点，使用二分查找来找到第一个大于根节点的索引位置，这样我们就能区分出左子树和右子树的区间范围，对左右子树的区间重复执行这个逻辑即可完成二叉搜索树的反序列化，题解如下：
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder builder = new StringBuilder();
preOrder(root, builder);
return builder.toString();
}
private void preOrder(TreeNode node, StringBuilder builder) {
if (node == null) {
return;
}
builder.append(node.val).append(",");
preOrder(node.left, builder);
preOrder(node.right, builder);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || "".equals(data)) {
return null;
}
String[] nodes = data.split(",");
return preOrder(nodes, 0, nodes.length - 1);
}
private TreeNode preOrder(String[] nodes, int left, int right) {
if (left > right) {
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(nodes[left]));
int l = left, r = right + 1;
while (l < r) {
int mid = l + r >> 1;
if (Integer.parseInt(nodes[mid]) > node.val) {
r = mid;
} else {
l = mid + 1;
}
}
node.left = preOrder(nodes, left + 1, l - 1);
node.right = preOrder(nodes, l, right);
return node;
}
本题的解题思路是每经历一个节点便减去该节点的值，之后再处理左子树和右子树，当到达叶子节点（左右子树为空）且总和为 0 时，则记录答案，需要注意的是，前序遍历完成进行回溯的时候，需要将节点值移除，题解如下：
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
preOrder(root, new LinkedList<>(), targetSum);
return res;
}
private void preOrder(TreeNode node, LinkedList<Integer> element, int sum) {
if (node == null) {
return;
}
sum -= node.val;
element.addLast(node.val);
if (sum == 0 && node.left == null && node.right == null) {
res.add((List<Integer>) element.clone());
}
preOrder(node.left, element, sum);
preOrder(node.right, element, sum);
element.removeLast();
}
根据题意，树 A 中的所有节点都可能成为 B 的根节点，那么我们需要将每个节点都作为根节点递归判断一次。在每次递归判断中，如果我们把 B 的所有节点都判断完了（B == null），则 B 为 A 的子结构，否则在 A 节点没有了但是 B 还有节点（A == null && B != null）或者节点值不等（A.val != B.val）则 B 不是 A 的子结构，题解如下：
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null) {
return false;
}
return doIsSubStructure(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
private boolean doIsSubStructure(TreeNode A, TreeNode B) {
if (B == null) {
return true;
}
if (A == null || A.val != B.val) {
return false;
}
return doIsSubStructure(A.left, B.left) && doIsSubStructure(A.right, B.right);
}
前序遍历会最先遍历到二叉树中底端最靠近左侧的节点，如果我们给每个节点编号，将每层最左侧节点的编号记录下来，每遍历到同层的其他节点就计算一次宽度，并记录宽度的最大值，那么我们能够轻易地得到结果，题解如下：
int res;
HashMap<Integer, Integer> depthNo;
public int widthOfBinaryTree(TreeNode root) {
res = 0;
depthNo = new HashMap<>();
preOrder(root, 0, 1);
return res;
}
private void preOrder(TreeNode node, int depth, int no) {
if (node == null) {
return;
}
if (!depthNo.containsKey(depth)) {
depthNo.put(depth, no);
}
res = Math.max(no - depthNo.get(depth) + 1, res);
preOrder(node.left, depth + 1, no << 2);
preOrder(node.right, depth + 1, no << 2 | 1);
}
本题需要根据二叉搜索树的性质（根节点大于任意左子树节点，根节点小于任意右子树节点）来验证“每一颗子树是否为二叉搜索树”，先验证当前树再去验证左右子树，我们从 left 指针开始遍历，找到左子树和右子树的区间范围，并判断右子树的右边界是否能够达到根节点索引的位置来判断当前树是否为二叉搜索树，题解如下：
public boolean verifyTreeOrder(int[] postorder) {
return doVerifyTreeOrder(postorder, 0, postorder.length - 1);
}
private boolean doVerifyTreeOrder(int[] postOrder, int left, int root) {
if (left >= root) {
return true;
}
int right = left;
while (right < postOrder.length && postOrder[right] < postOrder[root]) {
right++;
}
int tempRight = right;
while (tempRight < postOrder.length && postOrder[tempRight] > postOrder[root]) {
tempRight++;
}
return tempRight == root
&& doVerifyTreeOrder(postOrder, left, right - 1) && doVerifyTreeOrder(postOrder, right, root - 1);
}
前序遍历的顺序为“根左右”，那么我们每次取区间范围内的第一个元素即可确定当前根节点，但是我们不能只根据前序遍历去创建当前节点的左右子树，这时候我们就需要借助中序遍历了。
中序遍历的顺序是“左根右”，根据当前根节点值在中序遍历找到它对应的索引位置 index，那么 [left, index - 1] 即为在中序遍历中左子树的范围，[index + 1, right] 即为中序遍历中表示的右子树的区间范围，根据区间范围我们能获取到区间长度，那么我们根据区间长度即可确定前序遍历中左右子树的区间范围，题解如下：
public TreeNode buildTree(int[] preorder, int[] inorder) {
return doBuildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode doBuildTree(int[] preorder, int leftP, int rightP,
int[] inorder, int leftI, int rightI) {
if (leftP > rightP || leftI > rightI) {
return null;
}
TreeNode node = new TreeNode(preorder[leftP]);
// 确定根节点在中序遍历中的索引
int index = leftI;
while (index < inorder.length && inorder[index] != node.val) {
index++;
}
// 根据左子树区间长度确定前序遍历中左右子树的区间范围
int leftLength = index - leftI;
node.left = doBuildTree(preorder, leftP + 1, leftP + leftLength, inorder, leftI, index - 1);
node.right = doBuildTree(preorder, leftP + leftLength + 1, rightP, inorder, index + 1, rightI);
return node;
}
在节点值没有重复的情况下，以上题解每次确定根节点在中序遍历中的位置时都需要遍历中序遍历数组，我们可以借助 Map 将中序遍历中节点值和对应的索引保存下来，那么我们只需一次遍历就可以以 O(1) 的时间复杂度获取到对应的索引了，优化后的题解如下：
HashMap<Integer, Integer> nodeIndex;
public TreeNode buildTree(int[] preorder, int[] inorder) {
nodeIndex = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
nodeIndex.put(inorder[i], i);
}
return doBuildTree(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode doBuildTree(int[] preorder, int leftP, int rightP, int leftI, int rightI) {
if (leftP > rightP || leftI > rightI) {
return null;
}
TreeNode node = new TreeNode(preorder[leftP]);
// 确定根节点在中序遍历中的索引
int index = nodeIndex.get(node.val);
// 根据左子树区间长度确定前序遍历中左右子树的区间范围
int leftLength = index - leftI;
node.left = doBuildTree(preorder, leftP + 1, leftP + leftLength, leftI, index - 1);
node.right = doBuildTree(preorder, leftP + leftLength + 1, rightP, index + 1, rightI);
return node;
}