- 递归
- 层序遍历
- 二叉树非递归前中后序遍历
- 递归
- 层序遍历
- 二叉树非递归前中后序遍历
递归
几乎所有树的题都可以用递归解决，可以用递归解决的问题，也就可以用迭代的方法解决，因为递归调用就是一个出栈入栈的问题。
树结构
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}
二叉树的最大深度
后序递归
求出左右子树的深度，根的深度就是左子树深度和右子树深度中的最大值加1.
class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return 1 + Math.max(leftDepth, rightDepth);}}
二叉树最小深度
后序递归
求出左右子树的深度，根的深度就是左子树深度和右子树深度中的最小值加1。这里要注意左右子树深度为0的情况。
class Solution {public int minDepth(TreeNode root) {if (root == null) {return 0;}int left = minDepth(root.left);int right = minDepth(root.right);if (left == 0 || right == 0) {return left + right + 1;}return Math.min(left, right) + 1;}}
完全二叉树的节点个数
给出一个完全二叉树，求出该树的节点个数。
说明：完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。示例:输入:1/ \2 3/ \ /4 5 6输出: 6
后序递归
利用完全二叉树的性质，若左右子树高度相等，说明左子树是满，求右子树个数就行了；若左右子树高度不相等，说明右子树比左子树低一层，求左子树的具体个数就行。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if (leftDepth == rightDepth) {
return (int) Math.pow(2, leftDepth) + countNodes(root.right);
} else {
return (int) Math.pow(2, rightDepth) + countNodes(root.left);
}
}
private int getDepth(TreeNode root) {
int depth = 0;
while (root != null) {
depth++;
root = root.left;
}
return depth;
}
}
二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
注意：两结点之间的路径长度是以它们之间边的数目表示。
后序递归
求出左子树高度和右子树高度的最大值。有没有发现这跟求二叉树的最大深度很相似，这里只是多一个记录左子树高度和右子树高度的最大值而已。
class Solution {
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return max;
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
int left = depth(root.left);
int right = depth(root.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
}
}
平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
后序递归
这题不用我说的了吧，是不是跟上面三道题出奇的相似，只是把求二叉树直径变成了平衡二叉树的判断。
class Solution {
private boolean flag = true;
public boolean isBalanced(TreeNode root) {
maxDepth(root);
return flag;
}
private int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
if (Math.abs(leftDepth - rightDepth) > 1) {
flag = false;
}
return 1 + Math.max(leftDepth, rightDepth);
}
}
小总结
上面四道题其实就是二叉树的递归遍历，前、中和后序递归遍历的模板如下：
public void dfs(TreeNode root) {
if (root == null) {
return;
}
// 代码写在这里就是前序遍历
dfs(root.left);
// 代码写在这里就是中序遍历
dfs(root.right);
// 代码写在这里就是后序遍历
}
对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
递归解法
这里需要用根节点的左右孩子进行递归，因为这样比较方便判断，左右孩子是否符合条件。
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null) {
return false;
}
if (t1.val != t2.val) {
return false;
}
return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}
}
二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
后序递归
左孩子和右孩子进行递归交换，注意先把左孩子或者右孩子保存起来才能交换。很多朋友，表示理解不了递归，其实可以找一段视频看一下，每次入栈出栈是怎么回事，再把这里的题刷一刷，搞定递归不是问题。
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.right;
root.right = mirrorTree(root.left);
root.left = mirrorTree(temp);
return root;
}
}
98. 验证二叉搜索树
验证二叉搜索树、完全二叉树、满二叉树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
解法
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类 the root
* @return bool布尔型一维数组
*/
int count = 0;
public boolean isValidBST(TreeNode root) {
return validBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean validBST (TreeNode root, int low, int high) {
if (root == null) {
return true;
}
if (root.val < low || root.val > high) {
return false;
}
return validBST(root.left, low, root.val) && validBST(root.right, root.val, high);
}
// 验证完全二叉树
private boolean validCompleteTree(TreeNode root) {
/**
1.层次遍历直至遇到第一个空节点
2.完全二叉树在遇到空节点之后剩余的应当全是空节点
*/
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (queue.peek() != null) {
TreeNode node = queue.poll();
queue.add(node.left);
queue.add(node.right);
}
while (!queue.isEmpty() && queue.peek() == null) {
queue.poll();
}
return queue.isEmpty();
}
// 验证满二叉树
private boolean validFullTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int h = 0;
while (!queue.isEmpty()) {
int size = queue.size();
if ((int) Math.pow(2, h) != size) {
return false;
}
h++;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return true;
}
}
树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
递归解法
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}
boolean recur(TreeNode A, TreeNode B) {
if (B == null) {
return true;
}
if (A == null || A.val != B.val) {
return false;
}
return recur(A.right, B.right) && recur(A.left, B.left);
}
}
二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
前序递归
这题应该是比较简单的，拿root的值跟p、q的值对比，如果val < p.val && val < q.val说明，p、q最近公共祖先在右子树，如此递归轻松解决。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int val = root.val;
if (val < p.val && val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}
if (val > p.val && val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}
return root;
}
}
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
前序递归
看到这道题是不是有点懵逼，没有二叉搜索树的性质了，普通的二叉树怎么求最近公共祖先？仔细思考一下，其实就是三种情况，要么q是p的祖先，要么p是q的祖先，要么q和p是某一个节点的左右子树里面的节点。基于上面的分析，不难想到，我们依然可以通过递归遍历进行对比判断，代码如下：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 下面代码意思是，如果left为null，父节点为right;如果right为null,则父节点为left；如果
// left和right都不为null，说明父节点就是当前的root。
return left == null ? right : right == null ? left : root;
}
}
二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第k大的节点。
中序递归
利用二叉搜索树的性质，其中序遍历是递增有序的，所有我们给他来个中序遍历就搞定了。这也就是利用上面的递归遍历树的模板，在中间添一点代码就AC。
class Solution {
int k, res;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.right);
if (k == 0) {
return;
}
if (--k == 0) {
res = root.val;
}
dfs(root.left);
}
}
二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
前序递归
这依然是递归遍历树，先序遍历，满足条件就加入结果，不满足就继续递归。递归最后需要把最后一个节点值出栈，因为已经用完了，不需要这个值了。这里用双端队列模拟栈，因为stack是遗留类了不推荐使用，小技巧就是每次都入栈到尾部，这样从根节点开始就是有序的。
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
Deque<Integer> stack = new LinkedList<>();
dfs(root, stack, sum);
return res;
}
private void dfs(TreeNode root, Deque<Integer> stack, int sum) {
if (root == null) {
return;
}
stack.offerLast(root.val);
if (root.val == sum && root.left == null && root.right == null) {
res.add(new LinkedList<>(stack));
stack.pollLast();
return;
}
if (root.left != null) {
dfs(root.left, stack, sum - root.val);
}
if (root.right != null) {
dfs(root.right, stack, sum - root.val);
}
stack.pollLast();
}
}
538. 把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树
类中序递归
又是递归遍历，先遍历右孩子，再遍历根节点，然后遍历左孩子。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
dfs(root);
return root;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.right);
sum += root.val;
root.val = sum;
dfs(root.left);
}
}
669. 修剪二叉搜索树
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
前序递归
- root.val > high，说明root和root的右孩子都需要删除，所以递归遍历root的左孩子
- root.val < low，同理
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) {
return null;
}
if (root.val > high) {
return trimBST(root.left, low, high);
}
if (root.val < low) {
return trimBST(root.right, low, high);
}
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
找树左下角的值
给定一个二叉树，在树的最后一行找到最左边的值。
前序递归遍历
当height > max时，记录高度和当前结点的值，当前结点就是最左结点。
class Solution {
private int max = -1;
private int result = 0;
public int findBottomLeftValue(TreeNode root) {
dfs(root, 1);
return result;
}
private void dfs(TreeNode node, int height) {
if (node == null) {
return;
}
if (height > max) {
max = height;
result = node.val;
}
dfs(node.left, height + 1);
dfs(node.right, height + 1);
}
}
左叶子之和
计算给定二叉树的所有左叶子之和。
递归遍历
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
if (isLeaf(root.left)) {
return root.left.val + sumOfLeftLeaves(root.right);
}
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
private boolean isLeaf(TreeNode root) {
if (root == null) {
return false;
}
return root.left == null && root.right == null;
}
}
最长同值路径
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
后序递归
用一个path记录最长同值路径。
class Solution {
private int path = 0;
public int longestUnivaluePath(TreeNode root) {
dfs(root);
return path;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = dfs(root.left);
int right = dfs(root.right);
int leftDepth = root.left != null && root.val == root.left.val ? left + 1 : 0;
int rightDepth = root.right != null && root.val == root.right.val ? right + 1 : 0;
path = Math.max(path, leftDepth + rightDepth);
return Math.max(leftDepth, rightDepth);
}
}
二叉树中第二小的节点
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
递归遍历
class Solution {
public int findSecondMinimumValue(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) {
return -1;
}
int leftVal = root.left.val;
int rightVal = root.right.val;
if (leftVal == root.val) {
leftVal = findSecondMinimumValue(root.left);
}
if (rightVal == root.val) {
rightVal = findSecondMinimumValue(root.right);
}
if (leftVal != -1 && rightVal != -1) {
return Math.min(leftVal, rightVal);
}
if (leftVal == -1) {
return rightVal;
}
return leftVal;
}
}
572. 另一个树的子树
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
前序递归
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) {
return false;
}
return dfs(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean dfs(TreeNode s, TreeNode t) {
if (s == null && t == null) {
return true;
}
if (s == null || t == null || s.val != t.val) {
return false;
}
return dfs(s.left, t.left) && dfs(s.right, t.right);
}
}
合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
前序递归
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return null;
}
if (t1 == null) {
return t2;
}
if (t2 == null) {
return t1;
}
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
return root;
}
}
路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
前序递归
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null && root.val == sum) {
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
113. 路径总和 II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
前序递归
没啥好说的，前序递归遍历即可。
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
dfs(root, new LinkedList<Integer>(), sum);
return res;
}
private void dfs(TreeNode root, Deque<Integer> list, int sum) {
if (root == null) {
return;
}
list.offerLast(root.val);
if (root.left == null && root.right == null && root.val == sum) {
res.add(new LinkedList<Integer>(list));
list.pollLast();
return;
}
dfs(root.left, list, sum - root.val);
dfs(root.right, list, sum - root.val);
list.pollLast();
}
}
路径总和 III
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
前序递归
跟572. 另一个树的子树类似，可以对比一下。
class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int ret = dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
return ret;
}
private int dfs(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int ret = 0;
if (root.val == sum) {
ret++;
}
ret += dfs(root.left, sum - root.val) + dfs(root.right, sum - root.val);
return ret;
}
}
124. 二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
private int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 0 时，才会选取对应子节点
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
int curMaxSum = node.val + leftGain + rightGain;
// 更新最大路径和
maxSum = Math.max(maxSum, curMaxSum);
// 返回节点的最大贡献值
return node.val + Math.max(leftGain, rightGain);
}
}
打家劫舍 III
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
递归遍历
class Solution {
public int rob(TreeNode root) {
if (root == null) {
return 0;
}
int var1 = root.val;
if (root.left != null) {
var1 += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
var1 += rob(root.right.left) + rob(root.right.right);
}
int var2 = rob(root.left) + rob(root.right);
return Math.max(var1, var2);
}
}
剑指 Offer 36. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
递归解法
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node head, pre;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
dfs(root);
pre.right = head;
head.left = pre;
return head;
}
private void dfs(Node cur) {
if (cur == null) {
return;
}
dfs(cur.left);
if (pre == null) {
head = cur;
} else {
pre.right = cur;
}
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}
剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
递归遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private Map<Integer, Integer> indexMap;
private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
if (preorderLeft > preorderRight) {
return null;
}
// 前序遍历中的第一个节点就是根节点
// 在中序遍历中定位根节点
int inorderRoot = indexMap.get(preorder[preorderLeft]);
TreeNode root = new TreeNode(preorder[preorderLeft]);
// 得到左子树中的节点数目
int sizeLeftSubtree = inorderRoot - inorderLeft;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root.left = myBuildTree(preorder, inorder, preorderLeft + 1, preorderLeft + sizeLeftSubtree, inorderLeft, inorderRoot - 1);
root.right = myBuildTree(preorder, inorder, preorderLeft + sizeLeftSubtree + 1, preorderRight, inorderRoot + 1, inorderRight);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
indexMap = new HashMap<>();
// 构造哈希映射，帮助我们快速定位根节点
for (int i = 0; i < n; i++) {
indexMap.put(inorder[i], i);
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
}
剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
递归遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private StringBuilder serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append("None,");
} else {
sb.append(String.valueOf(root.val) + ",");
sb = serialize(root.left, sb);
sb = serialize(root.right, sb);
}
return sb;
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
return serialize(root, new StringBuilder()).toString();
}
private TreeNode deserialize(List<String> list) {
if (list.get(0).equals("None")) {
list.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
list.remove(0);
root.left = deserialize(list);
root.right = deserialize(list);
return root;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] array = data.split(",");
List<String> list = new LinkedList<String>(Arrays.asList(array));
return deserialize(list);
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
层序遍历
层序遍历顾名思义就是对树一层一层的遍历，显而易见把节点放入队列中，然后依次出队列就是层序遍历结果。
层序遍历模板
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> list = new ArrayList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// 可以进行一些操作
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
// 可以进行一些操作
}
return list;
}
}
剑指 Offer 32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> list = new ArrayList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
}
求二叉树深度
上面二叉树的最大深度也可以用层序遍历解决
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
queue.offer(new Pair(root, 1));
int maxDepth = Integer.MIN_VALUE;
while (!queue.isEmpty()) {
Pair<TreeNode, Integer> pair = queue.poll();
TreeNode node = pair.getKey();
int currentDepth = pair.getValue();
if (node != null) {
maxDepth = Math.max(currentDepth, maxDepth);
queue.offer(new Pair(node.left, currentDepth + 1));
queue.offer(new Pair(node.right, currentDepth + 1));
}
}
return maxDepth;
}
}
剑指 Offer 32 - II. 从上到下打印二叉树 II
剑指 Offer 32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(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.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
res.add(list);
}
return res;
}
}
剑指 Offer 32 - III. 从上到下打印二叉树 III
剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(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);
}
}
// 奇数时，翻转list
if (res.size() % 2 == 1) {
Collections.reverse(list);
}
res.add(list);
}
return res;
}
}
二叉树的层平均值
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
double sum = 0;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
sum += node.val;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
res.add(sum / size);
}
return res;
}
}
对称的二叉树
上面的对称的二叉树层序遍历解法如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode t1, TreeNode t2) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(t1);
queue.offer(t2);
while (!queue.isEmpty()) {
t1 = queue.poll();
t2 = queue.poll();
if (t1 == null && t2 == null) {
continue;
}
if (t1 == null || t2 == null || t1.val != t2.val) {
return false;
}
queue.offer(t1.left);
queue.offer(t2.right);
queue.offer(t1.right);
queue.offer(t2.left);
}
return true;
}
}
二叉树非递归前中后序遍历
上面的二叉树的递归遍历比较简单，下面就来看看二叉树的非递归遍历。
用Deque模拟栈，因为stack遗留类，不推荐使用
前序遍历
给定一个二叉树，返回它的 前序 遍历。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<>();
stack.offerFirst(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollFirst();
res.add(node.val);
// 先入右孩子，这样的话，左孩子先出栈
if (node.right != null) {
stack.offerFirst(node.right);
}
if (node.left != null) {
stack.offerFirst(node.left);
}
}
return res;
}
}
114. 二叉树展开为链表
给定一个二叉树，原地将它展开为一个单链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\
6
先序遍历
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
preorderTraversal(root, list);
int size = list.size();
for (int i = 1; i < size; i++) {
TreeNode prev = list.get(i - 1), curr = list.get(i);
prev.left = null;
prev.right = curr;
}
}
public void preorderTraversal(TreeNode root, List<TreeNode> list) {
if (root != null) {
list.add(root);
preorderTraversal(root.left, list);
preorderTraversal(root.right, list);
}
}
}
寻找前驱节点
解题的关键是：左子树的最下最右的节点，是右子树的父节点.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void flatten(TreeNode root) {
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode next = cur.left;
TreeNode preNode = next;
while (preNode.right != null) {
preNode = preNode.right;
}
preNode.right = cur.right;
cur.left = null;
cur.right = next;
}
cur = cur.right;
}
}
}
中序遍历
给定一个二叉树，返回它的中序 遍历。
思路：依然是用栈，先将左孩子全部入栈，与前序对比，其实就是改变了结点的入栈顺序。注：有栈为空的情况（没有左孩子），所有循环条件改成node != null || !stack.isEmpty()
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.offerFirst(node);
node = node.left;
}
node = stack.pollFirst();
res.add(node.val);
node = node.right;
}
return res;
}
}
后序遍历
给定一个二叉树，返回它的 后序 遍历。
后序遍历的倒序就是先访问根节点，然后访问右孩子，最后访问左孩子，所以改一改前序遍历就能得到结果。利用LinkedList的性质，可每次插入到链头，相当于翻转。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return new LinkedList<>();
}
LinkedList<Integer> res = new LinkedList<>();
Deque<TreeNode> stack = new LinkedList<>();
stack.addFirst(root);
while(!stack.isEmpty()) {
TreeNode node = stack.removeFirst();
// 利用LinkedList的性质，可每次插入到链头，相当于翻转。
res.addFirst(node.val);
if (node.left != null) {
stack.addFirst(node.left);
}
if (node.right != null) {
stack.addFirst(node.right);
}
}
return res;
}
}
欢迎关注我的公众号呦，率先更新内容，并且后续还有一些源码级的免费教程推出。
若有收获，就点个赞吧
0 人点赞
