树
94.中序遍历
输入：root = [1,null,2,3] 输出：[1,3,2]
解答
递归法
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
doInorderTraversal(root, result);
return result;
}
private void doInorderTraversal(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
doInorderTraversal(node.left, result);
result.add(node.val);
doInorderTraversal(node.right, result);
}
辅助栈迭代法
public List<Integer> inorderTraversal(TreeNode root) {
if(null == root){
return Collections.emptyList();
}
List<Integer> results = new ArrayList<>();
Stack<TreeNode> nodes = new Stack<>();
nodes.add(root);
if(null != root.left) {
injectLeftNode(root.left, nodes);
}
while (!nodes.isEmpty()) {
TreeNode node = nodes.pop();
results.add(node.val);
if (null != node.right) {
injectLeftNode(node.right, nodes);
}
}
return results;
}
private void injectLeftNode(TreeNode node, Stack<TreeNode> nodes) {
while (node != null) {
nodes.add(node);
node = node.left;
}
}
前序遍历
递归法
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
doPreorderTraversal(root, result);
return result;
}
private void doPreorderTraversal(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val);
doPreorderTraversal(node.left, result);
doPreorderTraversal(node.right, result);
}
辅助栈迭代法
public List<Integer> preorderTraversal(TreeNode root) {
if (null == root) {
return null;
}
List<Integer> results = new ArrayList<>();
Stack<TreeNode> nodeStack = new Stack<>();
nodeStack.push(root);
while (!nodeStack.isEmpty()) {
TreeNode cur = nodeStack.pop();
results.add(cur.val);
if(null != cur.right){
nodeStack.push(cur.right);
}
if(null != cur.left){
nodeStack.push(cur.left);
}
}
return results;
}
后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
doPostorderTraversal(root, result);
return result;
}
private void doPostorderTraversal(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
doPostorderTraversal(node.left, result);
doPostorderTraversal(node.right, result);
result.add(node.val);
}
辅助栈迭代法，根右左先序的reverse
public List<Integer> postorderTraversal(TreeNode root) {
if (null == root) {
return null;
}
List<Integer> results = new ArrayList<>();
Stack<TreeNode> nodeStack = new Stack<>();
nodeStack.push(root);
while (!nodeStack.isEmpty()) {
TreeNode cur = nodeStack.pop();
results.add(cur.val);
if(null != cur.left){
nodeStack.push(cur.left);
}
if(null != cur.right){
nodeStack.push(cur.right);
}
}
Collections.reverse(results);
return results;
}
102.二叉树的层序遍历
题目详情
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
题目解答
两个队列的方式
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
if(null == root){
return results;
}
Queue<TreeNode> cur = new LinkedList<>();
cur.add(root);
Queue<TreeNode> next = new LinkedList<>();
List<Integer> curResult = new ArrayList<>();
while (!cur.isEmpty()) {
TreeNode node = cur.poll();
curResult.add(node.val);
if(null != node.left){
next.add(node.left);
}
if(null != node.right){
next.add(node.right);
}
if(cur.isEmpty()){
cur = next;
next = new LinkedList<>();
results.add(curResult);
curResult = new ArrayList<>();
}
}
return results;
}
按层计数的方式，少一个队列
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
if(null == root){
return results;
}
Queue<TreeNode> cur = new LinkedList<>();
cur.add(root);
List<Integer> curResult = new ArrayList<>();
while (!cur.isEmpty()) {
int curSize = cur.size();
for (int i = 0; i < curSize; i++) {
TreeNode node = cur.poll();
curResult.add(node.val);
if(null != node.left){
cur.add(node.left);
}
if(null != node.right){
cur.add(node.right);
}
}
results.add(curResult);
curResult = new ArrayList<>();
}
return results;
}
105. 从前序与中序遍历序列构造二叉树
题目详情
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
题目解答
递归，根节点3，使用根节点在中序找到3，然后中序分割左子树和右子数
public TreeNode buildTree(int[] preorder, int[] inorder) {
return doBuild(preorder, inorder, 0, 0, preorder.length);
}
private TreeNode doBuild(int[] preorder, int[] inorder, int preSt, int inSt, int length) {
if(length == 0){
return null;
}
TreeNode root = new TreeNode(preorder[preSt]);
if(length == 1){
return root;
}
//find root in left
int i;
for (i = 0; i < length; i++) {
if (inorder[inSt + i] == root.val) {
root.left = doBuild(preorder, inorder, preSt + 1, inSt, i);
root.right = doBuild(preorder, inorder, preSt + i + 1, inSt + i + 1, length - i - 1);
return root;
}
}
return root;
}
226.反转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
题目解答
递归，非常简单且思路清晰 时间O(n) 空间O(h)，如果是平衡二叉树则为O(logn)
public TreeNode invertTree(TreeNode root) {
if(null == root){
return null;
}
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
层序遍历时翻转(我觉得没啥意义) 时间O(n) 空间O(n)
101.对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
题目解答
思路简单清晰，两棵树对称 = 根节点想等，左子树和右子树对称，右子树与左子数对称
public boolean isSymmetric(TreeNode root) {
return isSymmetric(root, root);
}
public boolean isSymmetric(TreeNode left, TreeNode right){
if(null == left && null == right){
return true;
}
if(null == left || null == right){
return false;
}
return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}
中序遍历
public boolean isSymmetric(TreeNode root) {
if(null == root){
return true;
}
Stack<TreeNode> left = new Stack<>();
Stack<TreeNode> right = new Stack<>();
left.add(root);
right.add(root);
while(!left.isEmpty() && !right.isEmpty() && (left.size() == right.size())){
TreeNode leftNode = left.pop();
TreeNode rightNode = right.pop();
if(leftNode == null && rightNode == null){
continue;
}
if(leftNode == null || rightNode == null){
return false;
}
if(leftNode.val != rightNode.val){
return false;
}
injectLeft(leftNode.right, left);
injectRight(rightNode.left, right);
}
return left.isEmpty() && right.isEmpty();
}
private void injectLeft(TreeNode node, Stack<TreeNode> left){
while(node != null){
left.add(node);
node = node.left;
}
}
private void injectRight(TreeNode node, Stack<TreeNode> right){
while(node != null){
right.add(node);
node = node.right;
}
}
辅助队列方法，比较简单
public boolean isSymmetric(TreeNode root) {
return isSymmetric(root, root);
}
public boolean isSymmetric(TreeNode left, TreeNode right) {
Queue<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.offer(left);
nodeQueue.offer(right);
while (!nodeQueue.isEmpty()) {
TreeNode node1 = nodeQueue.poll();
TreeNode node2 = nodeQueue.poll();
if(node1 == null && node2 == null){
continue;
}
if(node1 == null || node2 == null || node1.val != node2.val){
return false;
}
nodeQueue.offer(node1.left);
nodeQueue.offer(node2.right);
nodeQueue.offer(node1.right);
nodeQueue.offer(node2.left);
}
return true;
}
104.二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3 / \ 9 20
/ \ 15 7 返回它的最大深度 3 。
题目解答
层序遍历(其实没必要)
public int maxDepth(TreeNode root) {
if (null == root) {
return 0;
}
Queue<TreeNode> cur = new LinkedList<>();
cur.add(root);
int depth = 0;
while (!cur.isEmpty()) {
int curSize = cur.size();
for (int i = 0; i < curSize; i++) {
TreeNode node = cur.poll();
if (null != node.left) {
cur.add(node.left);
}
if (null != node.right) {
cur.add(node.right);
}
}
depth++;
}
return depth;
}
递归BFS，简单直观
public int maxDepth(TreeNode root) {
if (null == root) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth((root.right))) + 1;
}
二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 : 给定二叉树
1
/ \
2 3
/ \
4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
我自己的这个做法有点动态规划的味道，当前子数的最大值=左子树最大值，右子树最大值，左深度+右深度+1三者中最大的一个。
题目解答
public int diameterOfBinaryTree(TreeNode root) {
int[] depthAndNode = maxDepthAndPathNode(root);
return depthAndNode[1] - 1;
}
private int[] maxDepthAndPathNode(TreeNode node){
if(null == node){
return new int[]{0, 0};
}
int[] left = maxDepthAndPathNode(node.left);
int[] right = maxDepthAndPathNode(node.right);
int pathNode = Math.max(left[0] + right[0] + 1, Math.max(left[1], right[1]));
int maxDepth = Math.max(left[0], right[0]) + 1;
return new int[]{maxDepth, pathNode};
}
既然只是求最大值，其实迭代过程中计算即可
private int max;
public int diameterOfBinaryTree(TreeNode root) {
max = 0;
maxDepthAndPathNode(root);
return max - 1;
}
private int maxDepthAndPathNode(TreeNode node){
if(null == node){
return 0;
}
int left = maxDepthAndPathNode(node.left);
int right = maxDepthAndPathNode(node.right);
int curNodePath = left + right + 1;
max = Math.max(max, curNodePath);
return Math.max(left, right) + 1;
}
617. 合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null && root2 == null){
return null;
}
if(root1 == null){
return root2;
} else if(root2 == null){
return root1;
} else {
root1.val = root1.val + root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
}
96.不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
题目解答
动态规划，直接看了答案，不得不感叹动态规划最重要的还是无后效性的状态转移（比如到某个节点为止的xxx），其实程序算法基本上都是（比如排序后合并区间）。
- 确定的无后效性的状态转移即以i为根的二叉搜索树数 = 左子数二叉搜索树数 * 右子数二叉搜索树数
- f(i,n) 为以i为根的二叉搜索树数
- g(n) 为不同的二叉搜索树数
- f(i,n) = g(i-1) * g(n-i)
- g(n) = f(i,n)累加
- g(0) = 1
- g(1) = 1
public int numTrees(int n) {
int[] g = new int[n + 1];
g[0] = 1;
g[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
g[i] += g[j - 1] * g[i - j];
}
}
return g[n];
}
98. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
解答
递归方法，传递当前子树可以存在的最大值和最小值
public boolean isValidBST(TreeNode root) {
return validBSTAndMaxMin(root, Long.MAX_VALUE, Long.MIN_VALUE);
}
private boolean validBSTAndMaxMin(TreeNode node, Long max, Long min) {
if (node == null) {
return true;
}
if (node.val <= min || node.val >= max) {
return false;
}
return validBSTAndMaxMin(node.left, (long) node.val, min)
&& validBSTAndMaxMin(node.right, max, (long) node.val);
}
中序遍历，二叉搜索树的中序遍历是从小到大的
public boolean isValidBST(TreeNode root) {
if (null == root) {
return true;
}
long last = Long.MIN_VALUE;
Stack<TreeNode> nodeStack = new Stack<>();
injectLeftNode(root, nodeStack);
while (!nodeStack.isEmpty()) {
TreeNode node = nodeStack.pop();
if (last >= node.val) {
return false;
} else {
last = node.val;
}
injectLeftNode(node.right, nodeStack);
}
return true;
}
private void injectLeftNode(TreeNode node, Stack<TreeNode> nodeStack) {
while (node != null) {
nodeStack.add(node);
node = node.left;
}
}
2022-11-17
114.二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。
解答
前序递归
public void flatten(TreeNode root) {
if (root == null || (null == root.left && null == root.right)) {
return;
}
TreeNode left = root.left;
TreeNode right = root.right;
flatten(left);
flatten(right);
root.left = null;
if (null != left) {
root.right = left;
while(left.right != null){
left = left.right;
}
left.left = null;
left.right = right;
} else {
root.right = right;
}
}
前序迭代
public void flatten(TreeNode root) {
if (null == root) {
return;
}
Stack<TreeNode> nodeStack = new Stack<>();
TreeNode pre = new TreeNode(-1);
nodeStack.push(root);
while (!nodeStack.isEmpty()) {
TreeNode cur = nodeStack.pop();
if(null != cur.right){
nodeStack.push(cur.right);
}
if(null != cur.left){
nodeStack.push(cur.left);
}
pre.left = null;
pre.right = cur;
pre = cur;
}
}
寻找前驱节点，左子树的最右节点是右子数根节点的前驱节点。根->左子树根->左子树最右节点->右子树根
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;
}
}
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
解答
暴力回溯，查找出两个节点的所有祖先，然后比对。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> pAncestors = ancestors(root, p);
List<TreeNode> qAncestors = ancestors(root, q);
for (TreeNode pAncestor : pAncestors) {
for (TreeNode qAncestor : qAncestors) {
if (pAncestor.val == qAncestor.val) {
return pAncestor;
}
}
}
return null;
}
private List<TreeNode> ancestors(TreeNode root, TreeNode p){
List<TreeNode> ancestors = new ArrayList<>();
addAncestors(root, p, ancestors);
return ancestors;
}
private boolean addAncestors(TreeNode root, TreeNode p, List<TreeNode> ancestor){
if(null == root){
return false;
}
if(root.val == p.val){
ancestor.add(root);
return true;
}
if(addAncestors(root.left, p, ancestor) || addAncestors(root.right, p, ancestor)){
ancestor.add(root);
return true;
}
return false;
}
巧妙的递归方法。DFS，这就是一个后序遍历的模型，只不过是每个父节点都会接收子节点的状态（是否含有p、q）并把这个状态往上传递，直到该结点满足祖先节点的条件。这样一想就豁然开朗了。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
hasPOrQ(root, p, q);
return result;
}
private boolean hasPOrQ(TreeNode root, TreeNode p, TreeNode q) {
if (null == root) {
return false;
}
boolean lSon = hasPOrQ(root.left, p, q);
boolean rSon = hasPOrQ(root.right, p, q);
//1. 左右子树都有p和q，那么p,q分布在两边，当前节点为公共祖先
//2. 当前节点是p/q，左子树或右子树有p/q，pq一个为当前一个在任一子树
if ((lSon && rSon) || ((root.val == p.val || root.val == q.val) && (lSon || rSon))) {
//当首个公共祖先找到后，向上欺骗，该节点只包含一个，因此其他节点不会再被认为是祖先节点
result = root;
}
//左子树有p/q或右子树有p/q或当前节点是p/q
return lSon || rSon || root.val == p.val || root.val == q.val;
}
437. 路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
题目解答
回溯算法，性能不好，其实遍历只用了O(n)，但是有太多路径的更改增加操作，每个节点都需要循环路径
public int pathSum(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
doPath(root, targetSum, new LinkedList<>());
return num;
}
//路径要用long，因为大int累加会溢出
public void doPath(TreeNode node, int targetSum, LinkedList<Long> parentPaths) {
if (null == node) {
return;
}
if (node.val == targetSum) {
num++;
}
for (int i = 0; i < parentPaths.size(); i++) {
parentPaths.set(i, parentPaths.get(i) + node.val);
if (parentPaths.get(i) == targetSum) {
num++;
}
}
//添加当前路径
parentPaths.addLast((long) node.val);
doPath(node.left, targetSum, parentPaths);
doPath(node.right, targetSum, parentPaths);
//回溯
parentPaths.replaceAll(integer -> integer - node.val);
parentPaths.removeLast();
}
全部路径，重复遍历，路径总和 = 根节点开始的路径总和 + 左子树路径总和 + 右子树路径总和
public int pathSum(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
//每次递归都开出两条新的路径
//从当前节点出发的路径
int ret = rootSum(root, targetSum);
//从当前左子树出发的路径
ret += pathSum(root.left, targetSum);
//从当前右子树出发的路径
ret += pathSum(root.right, targetSum);
return ret;
}
public int rootSum(TreeNode node, long targetSum) {
if (null == node) {
return 0;
}
int num = 0;
if (node.val == targetSum) {
num++;
}
int leftRet = rootSum(node.left, targetSum - node.val);
int rightRet = rootSum(node.right, targetSum - node.val);
return num + leftRet + rightRet;
}
使用hash表对1方法进行改进，每次计算结果时，只需通过hash表查询，无需遍历路径
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> prefix = new HashMap<>();
prefix.put(0L, 1);
return dfs(root, prefix, 0, targetSum);
}
/**
*
* @param root 当前节点
* @param prefix 根节点到目标路径
* @param curr 根节点到目标节点的路径和
* @param targetSum 目标路径和
* @return
*/
public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
if (root == null) {
return 0;
}
curr += root.val;
int ret = prefix.getOrDefault(curr - targetSum, 0);
prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
ret += dfs(root.left, prefix, curr, targetSum);
ret += dfs(root.right, prefix, curr, targetSum);
//回溯
prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
return ret;
}
538. 把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。
题目解答
倒中序遍历 右中左
public TreeNode convertBST(TreeNode root) {
if (null == root || (null == root.left && null == root.right)) {
return root;
}
int preSum = 0;
Stack<TreeNode> nodeStack = new Stack<>();
injectRightNode(root, nodeStack);
while (!nodeStack.isEmpty()) {
TreeNode node = nodeStack.pop();
preSum += node.val;
node.val = preSum;
injectRightNode(node.left, nodeStack);
}
return root;
}
public TreeNode convertBST(TreeNode root) {
doSum(root);
return root;
}
private void doSum(TreeNode node){
if(node == null){
return;
}
doSum(node.right);
preSum += node.val;
node.val = preSum;
doSum(node.left);
}
