二叉树寻路
二叉树寻路
首先定位对应的label所属的层
判断是否起点属于偶数层，需要进行翻转
翻转之后的起点 start，通过是否属于偶数层进行翻转，获取实际节点值
class Solution {
public List<Integer> pathInZigZagTree(int label) {
//获取起始label所在的实际起始label与row
int row=1;int rowStart=1;
while(rowStart*2<=label){
row++;
rowStart*=2;
}
//当前行是否翻转
if(row%2==0){
label=getReverse(label,row);
}
List<Integer> res=new ArrayList<Integer>();
while(row>0){
if(row%2==0){
//需要反转
res.add(getReverse(label,row));
}else{
res.add(label);
}
row--;
label>>=1;
}
Collections.reverse(res);
return res;
}
//获取对应的翻转之后的元素位置
public int getReverse(int label,int row){//第i行区间为[(1<<(i-1),(1<<i)-1)]
return (1<<(row-1))+(1<<row)-1-label;
// return (1 << row - 1) + (1 << row) - 1 - label;
}
}
完全二叉树插入元素
完全二叉树添加元素
通过广度优先的方式记录下一个添加的位置
class CBTInserter {
Queue<TreeNode> queue=new LinkedList<TreeNode>();
TreeNode root;
public CBTInserter(TreeNode root) {
this.root=root;
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node=queue.peek();
if(node.left==null||node.right==null){
if(node.left!=null){
queue.offer(node.left);
}
break;
}
queue.poll();
queue.offer(node.left);
queue.offer(node.right);
}
}
public int insert(int val) {
TreeNode newNode=new TreeNode(val);
if(!queue.isEmpty()){
TreeNode node=queue.peek();
if(node.left==null){
node.left=newNode;
queue.offer(node.left);
// return node;
}else{
node.right=newNode;
queue.offer(node.right);
queue.poll();
// return node;
}
return node.val;
}
return -1;
}
public TreeNode get_root() {
return root;
}
}
翻转二叉树以匹配先序遍历
反转二叉树一匹配先序遍历
当不存在左孩子节点或者左孩子节点与先序遍历的结果一致，不需要进行翻转，直接进行先序遍历
当左孩子不为null,并且左孩子节点数值与下一个先序序列结果不一致，需要翻转 反线序遍历
当当前节点与先序序列不一致，不存在一种翻转方案
如果不存在反转方案，直接return
class Solution {
int[] voyage;
boolean flag=true;
int index=0;
List<Integer> res=new ArrayList<Integer>();
public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
this.voyage=voyage;
dfs(root);
return res;
}
public void dfs(TreeNode root){
if(root==null||!flag){
return;
}
if(root.val!=voyage[index]){//当前节点不能反转，直接比较
res.clear();
res.add(-1);
flag=false;
return;
}
index++;
//下一个节点
if(root.left==null||root.left.val==voyage[index]){
//继续先序遍历
dfs(root.left);
dfs(root.right);
}else{
//翻转
res.add(root.val);
dfs(root.right);
dfs(root.left);
}
}
}
克隆二叉树的相同节点
两棵二叉树同步遍历 dfs(original,cloned,target);
克隆二叉树相同节点
class Solution {
TreeNode res=null;
public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
dfs(original,cloned,target);
return res;
}
public void dfs(TreeNode original,TreeNode cloned,TreeNode target){
if(res!=null||original==null){
return ;
}
dfs(original.left,cloned.left,target);
if(original.val==target.val){
res=cloned;
}
dfs(original.right,cloned.right,target);
}
}
二叉树的着色游戏
二叉树着色游戏
二叉树的任何一个节点，最多将整棵树分成3部分
class Solution {
TreeNode xNode=null;
public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
//找到x节点
findTreeNode(root,x);
int theld=(n+1)/2;
int leftcount=subTreeCount(xNode.left);
if(leftcount>=theld){
return true;
}
int rightcount=subTreeCount(xNode.right);
if(rightcount>=theld){
return true;
}
return n-1-leftcount-rightcount>=theld;
}
public void findTreeNode(TreeNode root,int x){
if(xNode!=null||root==null){
return;
}
if(root.val==x){
xNode=root;
return;
}
findTreeNode(root.left,x);
findTreeNode(root.right,x);
}
//统计子树节点数
public int subTreeCount(TreeNode root){
if(root==null){
return 0;
}
return 1+subTreeCount(root.left)+subTreeCount(root.right);
}
}
从树的底层往上层进行分析，一层一层进行分析
class Solution {
int res=0;
public int distributeCoins(TreeNode root) {
//从底往上进行考虑，如果移动对应的过载量之后，底层的节点不需要考虑
dfs(root);
return res;
}
public int dfs(TreeNode root){
if(root==null){
return 0;
}
int left=dfs(root.left);
int right=dfs(root.right);
res+=Math.abs(left)+Math.abs(right);
return root.val-1+left+right;
}
}
路径和：从树上某一个节点出发和为目标值的路径数
class Solution {
public int pathSum(TreeNode root, int targetSum) {
//通过递归的方式
if(root==null){
return 0;
}
return pathSum(root.left,targetSum)+pathSum(root.right,targetSum)+dfs(root,targetSum);
}
public int dfs(TreeNode root,int target){
if(root==null){
return 0;
}
return (root.val==target? 1:0)+dfs(root.left,target-root.val)+dfs(root.right,target-root.val);
}
}
二叉搜索树的合并，给定二叉搜索树的集合 ，每一刻BST最多三个节点 ，将所有的树合并成一棵新的合理的二叉搜索树
二叉搜索树的合并
将所有的BST的叶子节点通过集合存储
对于根节点不在其他所有的树的叶子节点中的树的根节点，就可以作为新的二叉搜索树的根节点
/**
* 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 {
//存所有的叶节点
Set<Integer> leaves=new HashSet<Integer>();
//对于所有的树的根节点与树之间的映射
Map<Integer,TreeNode> candidates=new HashMap<Integer,TreeNode>();
int prev;
public TreeNode canMerge(List<TreeNode> trees) {
for(TreeNode tree:trees){
if(tree.left!=null){
leaves.add(tree.left.val);
}
if(tree.right!=null){
leaves.add(tree.right.val);
}
candidates.put(tree.val,tree);
}
for(TreeNode tree:trees){
if(!leaves.contains(tree.val)){
//作为根节点
candidates.remove(tree.val);
prev=0;//每一次合并将prev置为0
return (dfs(tree)&&candidates.size()==0)? tree:null;
}
}
//如果没有根节点
return null;
}
public boolean dfs(TreeNode root){
if(root==null){
return true;
}
if(root.left==null&&root.right==null&&candidates.containsKey(root.val)){
root.left=candidates.get(root.val).left;
root.right=candidates.get(root.val).right;
candidates.remove(root.val);
}
//递归左子树
if(!dfs(root.left)){
return false;
}
//当前节点,递归边界，是否是合法的二叉搜索树
if(root.val<=prev){//二叉搜索树的每一个节点值都是不相等的
return false;
}
prev=root.val;
return dfs(root.right);
}
}
二叉树上两个节点之间的最短路径 最近公共祖先
二叉树两个节点之间的最短路径
问题转化为两个节点之间的最近公共祖先
/**
* 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 {
Map<TreeNode,TreeNode> parent=new HashMap<TreeNode,TreeNode>();
TreeNode start,end;
public String getDirections(TreeNode root, int startValue, int destValue) {
//通过hash表记录每一个节点的父节点
dfs(root,startValue,destValue);
String s1=path(root,start);
String s2=path(root,end);
//获得公共祖先节点
int len=Math.min(s1.length(),s2.length());
int index=0;
for(int i=0;i<len;i++){
if(s1.charAt(i)!=s2.charAt(i)){
break;
}
index++;
}
char[] chs=new char[s1.length()-index];
Arrays.fill(chs,'U');
String res=new String(chs);
res+=s2.substring(index);
return res;
}
public void dfs(TreeNode root,int startValue,int destValue){
if(root.val==startValue){
start=root;
}
if(root.val==destValue){
end=root;
}
if(root.left!=null){
parent.put(root.left,root);
dfs(root.left,startValue,destValue);
}
if(root.right!=null){
parent.put(root.right,root);
dfs(root.right,startValue,destValue);
}
}
//通过parent获得根节点到两个节点路径
public String path(TreeNode root,TreeNode dest){
String res="";
while(dest.val!=root.val){
TreeNode par=parent.get(dest);
if(par.left!=null&&par.left.val==dest.val){
res+="L";
}else if(par.right!=null&&par.right.val==dest.val){
res+="R";
}
dest=par;
}
return new StringBuilder(res).reverse().toString();
}
}
判断一棵树是否是另一棵树的子树，空树不是任何一棵树得子树
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
//树的子结构判断
return (A!=null&&B!=null)&&(dfs(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B));
}
public boolean dfs(TreeNode p,TreeNode q){
if(q==null){
return true;
}
if(p==null||p.val!=q.val){
return false;
}
return dfs(p.left,q.left)&&dfs(p.right,q.right);
}
}
满二叉树的个数
满二叉树的个数
树中每一个节点都有0个或者2个孩子节点
/**
* 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 {
//通过记忆化搜索
Map<Integer,List<TreeNode>> mem=new HashMap<Integer,List<TreeNode>>();
public List<TreeNode> allPossibleFBT(int n) {
List<TreeNode> res=new ArrayList<TreeNode>();
if(mem.containsKey(n)){
return mem.get(n);
}
if(n==1){
res.add(new TreeNode(0));
}else if(n%2==1){
for(int x=0;x<n;x++){
int y=n-1-x;
for(TreeNode leftNode:allPossibleFBT(x)){
for(TreeNode rightNode:allPossibleFBT(y)){
TreeNode root=new TreeNode(0);
root.left=leftNode;
root.right=rightNode;
res.add(root);
}
}
}
mem.put(n,res);
}
return res;
}
}
