著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
给你二叉树的根结点 root ，请你将它展开为一个单链表：
TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
示例 1：
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [0] 输出：[0]
提示：
[0, 2000] 内-100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
前序遍历，原地递归修改
按照题意为前序遍历的结果，声明一个TreeNode pre记录前一个访问的节点
这样直接进行前序遍历，把当前节点挂载到pre节点的right上，记得要清除left节点
遍历当前节点的时候left、right节点的值记得先存下来，会在递归的时候被修改掉
class Solution {
/*
1
2 5
3 4 n 6
1
n 2
n 3
n 4
n 5
n 6
*/
TreeNode pre;
public void flatten(TreeNode root) {
dfs(root);
}
public void dfs(TreeNode node){
if (null == node){
return;
}
if (pre!=null){
pre.right = node;
}
pre = node;
TreeNode left = node.left;
TreeNode right = node.right;
node.left = null;
dfs(left);
dfs(right);
}
}给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000] 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11] 。
示例 2:
输入：root = [3,9,20,15,7] 输出：[3.00000,14.50000,11.00000]
提示：
[1, 104] 范围内-231 <= Node.val <= 231 - 1bfs
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if (null == root){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
double sum = 0;
int i=-1;
while (++i < size){
TreeNode node = queue.poll();
sum += (double) node.val;
if (node.left!=null){
queue.offer(node.left);
}
if (node.right!=null){
queue.offer(node.right);
}
}
res.add(sum/size);
}
return res;
}
}输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5] 输出: false
示例 2：
输入: [1,3,2,6,5] 输出: true
提示：
数组长度 <= 1000分段验证
分段验证
class Solution {
public boolean verifyPostorder(int[] postorder) {
return validate(postorder,0,postorder.length-1);
}
private boolean validate(int[] postorder, int left ,int right){
//如果左指针大于等于右指针了，说明当前节点以及没有子节点了，自然是符合条件的】
if (left>=right || left < 0 || right < 0) return true;
//找到这段数组对应的根节点，根据后序遍历的特性，即为这段数组的最后一位
int rootNum = postorder[right];
//初始赋值
int leftEnd = -1;
int rightStart = -1;
//开始遍历
for (int i = left; i < right; i++) {
if (postorder[i] < rootNum){
//如果这个值小于根节点的值，说明这个节点应该是在左子树中
leftEnd = i;
}
if (postorder[i] > rootNum && rightStart == -1){
//如果这个值大于根节点的值，说明这个节点应该是右子树上的
//且rightStart == -1 表示是第一次碰到的
rightStart = i;
}
}
//此时如果符合条件的话，应该是 leftEnd 在 rightStart 的左边一位
//或者 没有左子树：leftEnd == -1 且rightStart == left
//或者 没有右子树：rightStart == -1 且leftEnd == right-1
boolean validateResult = (leftEnd>-1 && rightStart> -1 && leftEnd+1== rightStart)
|| ( leftEnd == -1 && rightStart == left )
|| ( rightStart == -1 && leftEnd == right-1);
//自身验证完了，还要对分割好了的子序列的有效性判断
if (validateResult){
return validate( postorder, left, leftEnd ) && validate( postorder, rightStart, right-1 );
}
return false;
}
}输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
限制：
0 <= 节点个数 <= 5000
注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ Related Topics
👍 830👎 0
学二叉树入门必做题
关键信息
前中后序遍历
左右两个子节点的顺序不变都是先左子节点，后右子节点，区别就在于根节点是先遍历，还是中间，还是最后
这分别就是前中后序遍历
相关特性
现有如图这个一对前序遍历和中序遍历结果
根据相关特效，前序遍历的第一个就是根节点，所以我们知道了，根节点为3
又中序遍历中左侧只有一个，所以左子树只有一个节点9，右子树部分暂时不知道只知道剩下部分为右侧的前序和中序遍历结果，二叉树如下
再接下来，我们把右子树部分的按照同样的逻辑处理
我们知道了右子树的根节点为20，20的左子树只有一个节点15，右子树只有一个节点7
这样我们就重新构建完成了整棵二叉树
class Solution {
int[] preorder;
int[] inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
int len = preorder.length-1;
return buildTree(0,len,0,len);
}
public TreeNode buildTree( int preL, int preR, int inL, int inR){
if (preL > preR){
return null;
}
TreeNode node = new TreeNode(preorder[preL]);
int len = 0;
for (int i = inL; i <= inR; i++) {
if (inorder[i] == preorder[preL]){
len = i - inL;
}
}
node.left = buildTree(preL+1,preL+len,inL,inL+len-1);
node.right = buildTree(preL+len+1,preR,inL+len+1,inR);
return node;
}
}给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点2和节点8的最近公共祖先是6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点2和节点4的最近公共祖先是2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
注意：本题与主站 235 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
二叉搜索树特性
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val > q.val){
return lowestCommonAncestor(root,q,p);
}
if (root.val == p.val || root.val == q.val){
return root;
}
if (root.val > p.val && root.val > q.val){
return lowestCommonAncestor(root.left,p,q);
}
if (root.val < p.val && root.val < q.val){
return lowestCommonAncestor(root.right,p,q);
}
return root;
}
}class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val > q.val){
return lowestCommonAncestor(root,q,p);
}
TreeNode cur = root;
while ((cur.val > p.val && cur.val >q.val) || (cur.val < p.val && cur.val <q.val)){
if (cur.val > p.val && cur.val >q.val){
cur = cur.left;
}
if (cur.val < p.val && cur.val <q.val){
cur = cur.right;
}
}
return cur;
}
}比较简单，不做过多分析了
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
限制：
0 <= 树的结点个数 <= 10000注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/
DFS深搜模板套用
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
boolean isBalanced = true;
public boolean isBalanced(TreeNode root) {
dfs(root,0);
return isBalanced;
}
public int dfs(TreeNode node, int dep){
if (!isBalanced || null == node){
return dep;
}
dep++;
int leftDep = dfs(node.left,dep);
int rightDep = dfs(node.right,dep);
if (Math.abs(leftDep-rightDep )< 2){
return Math.max(leftDep,rightDep);
}
isBalanced = false;
return Math.max(leftDep,rightDep);
}
}给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
示例 1:
输入：root = [4,2,7,1,3], val = 2 输出：[2,1,3]
Example 2:
输入：root = [4,2,7,1,3], val = 5 输出：[]
提示：
[1, 5000] 范围内1 <= Node.val <= 107root 是二叉搜索树1 <= val <= 107根据二叉搜索树的左小右大的特性【递归&遍历树】
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null){
return null;
}
if (root.val == val){
return root;
}
return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val);
}
}应该没啥特殊的，二叉搜索树的特性
左子节点 < 根节点 < 右子节点所以照着这个写就行了
也可以改递归为遍历的写法，毕竟 递归和遍历循环是可以相互转化的
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while (root !=null){
if (root.val == val) return root;
root = root.val > val? root.left : root.right;
}
return root;
}
}