NC刷题笔记3-树
- NC5 二叉树根节点到叶子节点的所有路径和
- NC6 二叉树中的最大路径和
- NC8 二叉树中和为某一值的路径(二)
- NC9 二叉树中和为某一值的路径(一)
- NC11 将升序数组转化为平衡二叉搜索树
- NC12 重建二叉树
- NC13 二叉树的最大深度
- NC14 按之字形顺序打印二叉树
- NC15 求二叉树的层序遍历
- NC16 对称的二叉树
- NC 45 二叉树前序、中序和后序遍历
- NC 58找到两个错误结点
- NC60 判断一棵二叉树是否为搜索二叉树和完全二叉树
- NC62判断是不是平衡二叉树
- NC72 二叉树镜像
- NC80 把二叉树打印成多行
- NC81 二叉搜索树的第k个节点
- NC84 完全二叉树结点数
- NC98 判断t1树中是否有与t2树完全相同的子树
- NC102 在二叉树中找到两个节点的最近公共祖先
- NC117 合并二叉树
- NC123 序列化二叉树
- NC136 输出二叉树右视图
NC5 二叉树根节点到叶子节点的所有路径和
描述
给定一个二叉树的根节点root，该树的节点值都在数字0−9 之间，每一条从根节点到叶子节点的路径都可以用一个数字表示。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n
例如根节点到叶子节点的一条路径是31→2→3,那么这条路径就用 123 来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：
这颗二叉树一共有两条路径，
根节点到叶子节点的路径 21→2 用数字 12 代替
根节点到叶子节点的路径 31→3 用数字 13 代替
所以答案为 12+13=25
数据范围：节点数 1000≤n≤100，保证结果在32位整型范围内
要求：空间复杂度 O(n)，时间复杂度 O(n^2)
进阶：空间复杂度 O(n)，时间复杂度 O(n)
示例1
输入：{1,2,3}
返回值：25
示例2
输入：{1,0}
返回值：10
示例3
输入：{1,2,0,3,4}
返回值：257
思路： 先序遍历（根 左右）
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/
* @param root TreeNode类
* @return int整型
*/
public int sumNumbers(TreeNode root) {
int sum = 0;
if (root == null) {
return sum;
}
return preorderSumNumbers(root, sum);
}
public int preorderSumNumbers(TreeNode root, int sum) {
if (root == null) return 0;
sum = sum * 10 + root.val;
if (root.left == null && root.right == null) {
return sum;
}
return preorderSumNumbers(root.left, sum) + preorderSumNumbers(root.right, sum);
}
}
NC6 二叉树中的最大路径和
描述
二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。
注意:
1.同一个节点在一条二叉树路径里中最多出现一次
2.一条路径至少包含一个节点，且不一定经过根节点
给定一个二叉树的根节点root，请你计算它的最大路径和
/*
* 124. Binary Tree Maximum Path Sum
* 解题思路：
* 这道题是求树的路径和的题目，不过和平常不同的是这里的路径不仅可以从根到某一个结点，
* 而且路径可以从左子树某一个结点，然后到达右子树的结点，就像题目中所说的可以起始和终结于任何结点。
* 在这里树没有被看成有向图，而是被当成无向图来寻找路径。
* 因为这个路径的灵活性，我们需要对递归返回值进行一些调整，而不是通常的返回要求的结果。
* 在这里，函数的返回值定义为以自己为根的一条从根到子结点的最长路径（这里路径就不是当成无向图了，
* 必须往单方向走）。
* 这个返回值是为了提供给它的父结点计算自身的最长路径用，
* 而结点自身的最长路径（也就是可以从左到右那种）则只需计算然后更新即可。
* 这样一来，一个结点自身的最长路径就是它的左子树返回值（如果大于0的话），
* 加上右子树的返回值（如果大于0的话），再加上自己的值。
* 而返回值则是自己的值加上左子树返回值，
* 右子树返回值或者0（注意这里是“或者”，而不是“加上”，因为返回值只取一支的路径和）。
* 在过程中求得当前最长路径时比较一下是不是目前最长的，如果是则更新。
* 算法的本质还是一次树的遍历，所以复杂度是O(n)。而空间上仍然是栈大小O(logn)。
*/
import java.util.*;
public class Solution {
int maxValue = 0;
public int maxPathSum(TreeNode root) {
if (root == null) return 0;
maxValue = Integer.MIN_VALUE;
getMaxPathSum(root);
return maxValue;
}
private int getMaxPathSum(TreeNode root) {
if (root == null) return 0;
//因为节点的值可以为负数，所以最大值取0和子树值的较大者
int leftMax = Math.max(0, getMaxPathSum(root.left));
int rightMax = Math.max(0, getMaxPathSum(root.right));
//如果将当前root作为根节点，那么最大值是root.val+左子树最大值+右子树最大值
maxValue = Math.max(maxValue, root.val + leftMax + rightMax);
//只能返回左右子树中较大值加上root.val
return Math.max(0, root.val + Math.max(leftMax, rightMax));
}
}
NC8 二叉树中和为某一值的路径(二)
描述
输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n
如二叉树root为{10,5,12,4,7},expectNumber为22
则合法路径有[[10,5,7],[10,12]]
数据范围:
树中节点总数在范围 [0, 5000] 内
-1000 <= 节点值 <= 1000
-1000 <= expectNumber <= 1000
示例1 输入：{10,5,12,4,7},22 返回值：[[10,5,7],[10,12]] 说明：返回[[10,12],[10,5,7]]也是对的
示例2 输入：{10,5,12,4,7},15 返回值：[]
示例3 输入：{2,3},0 返回值：[]
示例4 输入：{1,3,4},7 返回值：[]
思路1：
前序遍历 递归调用
import java.util.ArrayList;
public class Solution {
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> temp=new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
recur(root,target);
return res;
}
public void recur(TreeNode root,int target){
if(root==null) return;
temp.add(root.val);
target=target-root.val;
if(root.left==null&&root.right==null&&target==0){
res.add(new ArrayList<Integer>(temp));
target+=root.val;
temp.remove(temp.size()-1);
return;
}
recur(root.left,target);
recur(root.right,target);
target+=root.val;
temp.remove(temp.size()-1);
}
}
NC9 二叉树中和为某一值的路径(一)
描述
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n
例如：
给出如下的二叉树，sum=22，
返回true，因为存在一条路径5→4→11→2的节点值之和为 22
数据范围：
1.树上的节点数满足0≤n≤10000
2.每个节点的值都满足0<∣val∣≤1000
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(树的高度)，时间复杂度 O(n)
示例1 输入：{5,4,8,1,11,#,9,#,#,2,7},22 返回值：true
示例2 输入：{1,2},0 返回值：false
示例3 输入：{1,2},3 返回值：true
示例4 输入：{},0 返回值：false
思路：前序遍历
import java.util.*;
public class Solution {
public boolean hasPathSum (TreeNode root, int sum) {
// write code here
if(root==null) return false;
sum=sum-root.val;
if(root.left==null&&root.right==null&&sum==0) return true;
return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);
}
}
NC11 将升序数组转化为平衡二叉搜索树
描述
给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.
平衡二叉搜索树指树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1
数据范围：0≤n≤10000，数组中每个值满足∣val∣≤5000
进阶：空间复杂度 O(n)，时间复杂度 O(n)
例如当输入的升序数组为[-1,0,1,2]时，转化后的平衡二叉搜索树（BST）可以为{1,0,2,-1}，如下图所示：
示例1
输入：[-1,0,1,2]
返回值：{1,0,2,-1}
示例2
输入：[]
返回值：{}
思路：
取数组中间结点为根节点，左侧为左子树，右侧为右子树
递归构造
import java.util.*;
public class Solution {
public TreeNode sortedArrayToBST(int[] num) {
if (num.length == 0) return null;
return sortedArrayToBST(num, 0, num.length - 1);
}
public TreeNode sortedArrayToBST(int[] num, int start, int end) {
if (start > end) return null;
int mid = (start + end+1) >> 1;
TreeNode root = new TreeNode(num[mid]);
root.left = sortedArrayToBST(num, start, mid - 1);
root.right = sortedArrayToBST(num, mid + 1, end);
return root;
}
}
NC12 重建二叉树
描述
给定节点数为 n 二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点，系统会自动输出整颗树做答案对比
数据范围：0n≤2000，节点的值 0≤val≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)
思路：
递归调用
public class Solution {
int[] pre;
HashMap<Integer,Integer> inOrder=new HashMap<Integer,Integer>();
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
this.pre=pre;
for(int i=0;i<vin.length;i++) inOrder.put(vin[i],i);
return reBuild(0,0,vin.length-1);
}
public TreeNode reBuild(int preindex,int left,int right){
if(left>right) return null;
TreeNode root=new TreeNode(pre[preindex]);
root.left=reBuild(preindex+1,left,inOrder.get(pre[preindex])-1);
root.right=reBuild(preindex+inOrder.get(pre[preindex])-left+1,inOrder.get(pre[preindex])+1,right);
return root;
}
}
NC13 二叉树的最大深度
描述
求给定二叉树的最大深度，深度是指树的根节点到任一叶子节点路径上节点的数量。最大深度是所有叶子节点的深度的最大值。（注：叶子节点是指没有子节点的节点。）
数据范围：0≤n≤100000，树上每个节点的val满足∣val∣≤100
要求： 空间复杂度 O(1),时间复杂度 O(n)
示例1 输入：{1,2} 返回值：2
示例2 输入：{1,2,3,4,#,#,5} 返回值：3
思路：
递归，直接往下面遍历
import java.util.*;
public class Solution {
public int maxDepth (TreeNode root) {
if(root==null) return 0;
if(root.left==null&&root.right==null) return 1;
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}
NC14 按之字形顺序打印二叉树
输入：
二叉树
1
2 3
4 5
输出：
[[1],
[3,2],
[4,5]]
思路1:
1 双端队列，用于存放二叉树结点信息
2 用链表存储每层的信息，奇数从左到右，偶数从右向左
import java.util.*;
public class Solution {
ArrayList<Integer> temp=new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
if(pRoot==null) return res;
int index=1;
queue.offer(pRoot);
while(!queue.isEmpty()){
int n=queue.size();
temp=new ArrayList<Integer>();
for(int i=0;i<n;i++){
TreeNode node= queue.poll();
if(index%2==1){
temp.add(node.val);
}else{
temp.add(0,node.val);
}
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
res.add(temp);
index++;
}
return res;
}
}
NC15 求二叉树的层序遍历
思路：栈
import java.util.*;
public class Solution {
ArrayList<Integer> temp=new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
if(root==null) return res;
queue.offer(root);
while(!queue.isEmpty()){
int n=queue.size();
temp=new ArrayList<Integer>();
for(int i=0;i<n;i++){
TreeNode node= queue.poll();
temp.add(node.val);
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
res.add(temp);
}
return res;
}
}
NC16 对称的二叉树
判断二叉树是否是镜像二叉树
思路1：递归
思路2：层序遍历 空值用#代替
思路1：
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot==null||(pRoot.left==null&&pRoot.right==null)) return true;
return recur(pRoot.left,pRoot.right);
}
boolean recur(TreeNode left,TreeNode right){
if(left==null&&right==null) return true;
if((left==null&&right!=null)||(left!=null&&right==null)||(left.val!=right.val)) return false;
return recur(left.left,right.right)&&recur(left.right,right.left);
}
}
NC 45 二叉树前序、中序和后序遍历
描述
给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。
数据范围：0≤n≤1000，树上每个节点的val值满足0≤val≤100
要求：空间复杂度 O(n)，时间复杂度 O(n)
示例1 输入：{1,2,3} 返回值：[[1,2,3],[2,1,3],[2,3,1]]
示例2 输入：{} 返回值：[[],[],[]]
思路1：递归
思路2：非递归
import java.util.*;
public class Solution {
ArrayList<Integer> pre=new ArrayList<>();
ArrayList<Integer> in=new ArrayList<>();
ArrayList<Integer> post=new ArrayList<>();
public int[][] threeOrders (TreeNode root) {
preOrder(root);
inOrder(root);
postOrder(root);
return getRes();
}
public void preOrder(TreeNode root){
if(root==null) return;
pre.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
public void inOrder(TreeNode root){
if(root==null) return;
inOrder(root.left);
in.add(root.val);
inOrder(root.right);
}
public void postOrder(TreeNode root){
if(root==null) return;
postOrder(root.left);
postOrder(root.right);
post.add(root.val);
}
public int[][] getRes(){
int[][] res =new int[3][pre.size()];
for(int i=0;i<pre.size();i++){
res[0][i]=pre.get(i);
res[1][i]=in.get(i);
res[2][i]=post.get(i);
}
return res;
}
}
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
ArrayList<Integer> pre=new ArrayList<>();
ArrayList<Integer> in=new ArrayList<>();
ArrayList<Integer> post=new ArrayList<>();
public int[][] threeOrders (TreeNode root) {
preOrder(root);
inOrder(root);
postOrder(root);
return getRes();
}
public void preOrder(TreeNode root){
if(root==null) return;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur=stack.pop();
pre.add(cur.val);
if(cur.right!=null) stack.push(cur.right);
if(cur.left!=null) stack.push(cur.left);
}
}
public void inOrder(TreeNode root){
if(root==null) return;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur=root;
while(!stack.isEmpty()||cur!=null){
if(cur!=null){
stack.push(cur);
cur=cur.left;
}else{
cur= stack.pop();
in.add(cur.val);
cur=cur.right;
}
}
}
public void postOrder(TreeNode root){
if(root==null) return;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur=stack.pop();
post.add(0,cur.val);
if(cur.left!=null) stack.push(cur.left);
if(cur.right!=null) stack.push(cur.right);
}
}
public int[][] getRes(){
int[][] res =new int[3][pre.size()];
for(int i=0;i<pre.size();i++){
res[0][i]=pre.get(i);
res[1][i]=in.get(i);
res[2][i]=post.get(i);
}
return res;
}
}
NC 58找到两个错误结点
描述
一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)
搜索二叉树：满足每个节点的左子节点小于当前节点，右子节点大于当前节点。
进阶：空间复杂度 O(1)，时间复杂度 O(n)
示例1 输入：{1,2,3} 返回值：[1,2]
示例2 输入：{4,2,5,3,1} 返回值：[1,3]
思路1：
数组，中序遍历，从左往右找一个，从右往左找一个
思路2：
递归
import java.util.*;
public class Solution {
List<Integer> list=new ArrayList<>();
public int[] findError (TreeNode root) {
inOrder(root);
int left=0,right=list.size()-1;
int[] res=new int[2];
while(list.get(left)<list.get(left+1)) left++;
while(list.get(right)>list.get(right-1)) right--;
res[0]=list.get(right);
res[1]=list.get(left);
return res;
}
public void inOrder(TreeNode root){
if(root==null) return;
Stack<TreeNode> stack=new Stack<>();
TreeNode cur=root;
while(!stack.isEmpty()||cur!=null){
if(cur!=null){
stack.push(cur);
cur=cur.left;
}else{
cur= stack.pop();
list.add(cur.val);
cur=cur.right;
}
}
}
}
import java.util.*;
public class Solution {
int[] result = new int[2];
int index = 1;
TreeNode preNode;
public int[] findError (TreeNode root) {
if(root == null) return result;
findError(root.left);
if(preNode == null) preNode = root;
if(index == 1 && root.val < preNode.val) {
result[index] = preNode.val;
index--;
}
if(index == 0 && root.val < preNode.val) {
result[index] = root.val;
}
preNode = root;
findError(root.right);
return result;
}
}
NC60 判断一棵二叉树是否为搜索二叉树和完全二叉树
描述
给定一棵二叉树，已知其中的节点没有重复值，请判断该二叉树是否为搜索二叉树和完全二叉树。
输出描述：分别输出是否为搜索二叉树、完全二叉树。
数据范围：二叉树节点数满足 0 \le n \le 5000000≤n≤500000 ，二叉树上的值满足 0 \le val \le 1000000≤val≤100000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
注意：空子树我们认为同时符合搜索二叉树和完全二叉树。
示例1
输入：
{2,1,3}
复制
返回值：
[true,true]
复制
示例2 输入：{1,#,2} 返回值：[true,false]
说明：由于节点的右儿子大于根节点，无左子树，所以是搜索二叉树但不是完全二叉树
示例3 输入：{} 返回值：[true,true]
思路：
1 判断二叉搜索树 当前结点的值比前一个小
2 判断完全二叉树
层序遍历，false的情况：（左节点为空&&右节点不为空） 或 （是叶结点但是左右结点不全为空）
import java.util.*;
public class Solution {
public boolean[] judgeIt (TreeNode root) {
boolean[] res = new boolean[2];
res[0] = isSerachTreeBST(root);
res[1] = isAllTreeBST(root);
return res;
}
long pre = Long.MIN_VALUE;
public boolean isSerachTreeBST(TreeNode root){
if(root == null)return true;
if (!isSerachTreeBST(root.left)) return false;
if (root.val <= pre) return false;
pre = root.val;
return isSerachTreeBST(root.right);
}
public boolean isAllTreeBST(TreeNode root){
if(root == null) return true;
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
TreeNode left = null;
TreeNode right = null;
boolean flag = false; //标记是否遇到节点不双全的节点
while(!queue.isEmpty()){
root = queue.poll();
left = root.left;
right = root.right;
//遇到左右孩子不双全的节点并且该节点不是叶子节点的时候就不是完全二叉树 //左孩子为空并且右孩子不为空的时候不是完全二叉树
if((flag && !(left == null && right == null)) || (left == null && right != null)){
return false;
}
if(left != null) queue.offer(left);
if(right != null) queue.offer(right);
if(left == null || right == null) flag = true;
}
return true;
}
}
NC62判断是不是平衡二叉树
思路：
递归判断每个结点高度差是否符合条件
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root==null) return true;
int n=Math.abs(height(root.left)-height(root.right));
return (n<=1)&&IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
}
public int height(TreeNode root){
if(root==null) return 0;
if(root.left==null && root.right==null) return 1;
return Math.max( height(root.left),height(root.right) )+1;
}
}
NC72 二叉树镜像
思路：递归
import java.util.*;
public class Solution {
public TreeNode Mirror (TreeNode pRoot) {
if(pRoot==null) return pRoot;
TreeNode left=pRoot.left;
TreeNode right=pRoot.right;
pRoot.left=Mirror(right);
pRoot.right=Mirror(left);
return pRoot;
}
}
NC80 把二叉树打印成多行
思路：层序遍历
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer> > res=new ArrayList<ArrayList<Integer> >();
ArrayList<Integer> temp=new ArrayList<Integer>();
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
Queue<TreeNode> stack=new LinkedList<>();
if(pRoot==null) return res;
stack.offer(pRoot);
while(!stack.isEmpty()){
int n=stack.size();
temp=new ArrayList<Integer>();
for(int i=0;i<n;i++){
TreeNode t=stack.poll();
temp.add(t.val);
if(t.left!=null) stack.offer(t.left);
if(t.right!=null) stack.offer(t.right);
}
res.add(temp);
}
return res;
}
}
NC81 二叉搜索树的第k个节点
思路： 中序遍历
import java.util.*;
public class Solution {
ArrayList<Integer> list=new ArrayList<>();
public int KthNode (TreeNode proot, int k) {
inOrder(proot);
return k==0?-1:k>list.size()?-1:list.get(k-1);
}
public void inOrder(TreeNode root){
if(root==null) return;
inOrder(root.left);
list.add(root.val);
inOrder(root.right);
}
}
NC84 完全二叉树结点数
思路1：递归树的遍历 时间复杂度O（n） 空间复杂度O（n）
思路2：非递归树的遍历 时间复杂度O（n） 空间复杂度O（n）
思路2：利用完全二叉树的性质 时间复杂度O((logn)^2) 空间复杂度O(logn)
1 满二叉树结点个数 2^h
2 完全二叉树
① 左右高度相等 左为满
② 左右高度不等 右为满
思路1：
public class Solution {
int index=0;
public int nodeNum(TreeNode head) {
preOrder(head);
return index;
}
public void preOrder(TreeNode root){
if(root==null) return;
preOrder(root.left);
index++;
preOrder(root.right);
}
}
思路2：
import java.util.*;
public class Solution {
int index=0;
public int nodeNum(TreeNode head) {
preOrder(head);
return index;
}
public void preOrder(TreeNode root){
if(root==null) return;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node= stack.pop();
index++;
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
}
}
}
思路3：
public class Solution {
public int nodeNum(TreeNode head) {
if(head == null) return 0;
int rightHeight = complateTreeHeight(head.right);
int leftHeight = complateTreeHeight(head.left);
if(rightHeight == leftHeight){
return (int)Math.pow(2, leftHeight) + nodeNum(head.right);
}else {
return (int)Math.pow(2, rightHeight) + nodeNum(head.left);
}
}
public int complateTreeHeight(TreeNode root){
int count = 0;
while (root != null){
count++;
root = root.left;
}
return count;
}
}
NC98 判断t1树中是否有与t2树完全相同的子树
描述
给定彼此独立的两棵二叉树，树上的节点值两两不同，判断 t1 树是否有与 t2 树完全相同的子树。子树指一棵树的某个节点的全部后继节点。数据范围：树的节点数满足0<n≤500000，树上每个节点的值一定在32位整型范围内
进阶：空间复杂度: O(1)，时间复杂度 O(n)
示例1 输入：{1,2,3,4,5,6,7,#,8,9},{2,4,5,#,8,9} 返回值：true 备注：1≤n≤500000
思路1：递归
思路2：前序遍历+strings.contains()
import java.util.*;
public class Solution {
public boolean isContains (TreeNode root1, TreeNode root2) {
if(root1==null) return false;
if(root1==null&&root2==null) return true;
return isContains(root1.left,root2)||isContains(root1.right,root2)||isEqual(root1,root2);
}
public boolean isEqual(TreeNode root1, TreeNode root2){
if(root1==null && root2==null) return true;
if(root1==null||root2==null||root1.val!=root2.val) return false;
return isEqual(root1.left,root2.left) && isEqual(root1.right,root2.right);
}
}
public class Solution {
public boolean isContains(TreeNode root1, TreeNode root2) {
// 利用先序遍历序列化两颗二叉树
String str1 = preorder(root1);
String str2 = preorder(root2);
// 然后判断str1是否包含str2即可
return str1.contains(str2);
}
// 返回先序遍历后的字符串
private String preorder(TreeNode root) {
if (root == null) return "#";
return root.val + ","+ preorder(root.left) +"," + preorder(root.right) ;
}
}
NC102 在二叉树中找到两个节点的最近公共祖先
思路：
递归 寻找两个结点的最近祖先
import java.util.*;
public class Solution {
public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
return helper(root, o1, o2).val;
}
public TreeNode helper(TreeNode root, int o1, int o2) {
if (root == null || root.val == o1 || root.val == o2) return root;
TreeNode left = helper(root.left, o1, o2);
TreeNode right = helper(root.right, o1, o2);
//如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果即可
if (left == null) return right;
if (right == null) return left;
//如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
//我们只需要返回cur结点即可。
return root;
}
}
NC117 合并二叉树
描述
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：
两颗二叉树是:
1
/ \
3 2
/
5
2
/ \
1 3
\ \
4 7
3
/ \
4 5
/ \ \
5 4 7
思路：
递归遍历
import java.util.*;
public class Solution {
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
if(t1 == null) return t2;
if(t2 == null) return t1;
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
NC123 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）
二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}"，再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。
当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。
数据范围：节点数n≤100，树上每个节点的值满足0≤val≤150
要求：序列化和反序列化都是空间复杂度 O(n)，时间复杂度 O(n)
示例1
输入：{1,2,3,#,#,6,7}
返回值：{1,2,3,#,#,6,7}
示例2
输入：{8,6,10,5,7,9,11}
返回值：{8,6,10,5,7,9,11}
思路：
序列化：递归先序遍历
反序列化：递归先序解码
public class Solution {
public String Serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if(root == null){
sb.append("#,");
return sb.toString();
}
sb.append(root.val + ",");
sb.append(Serialize(root.left));
sb.append(Serialize(root.right));
return sb.toString();
}
int index = -1; //计数变量
public TreeNode Deserialize(String str) {
index++;
String[] strr = str.split(",");
TreeNode node = null;
if(!strr[index].equals("#")){
node = new TreeNode(Integer.valueOf(strr[index]));
node.left = Deserialize(str);
node.right = Deserialize(str);
}
return node;
}
}
NC136 输出二叉树右视图
描述
请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
数据范围： 0≤n≤10000
要求： 空间复杂度 O(n)，时间复杂度 O(n)
如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：
示例1 输入：[1,2,4,5,3],[4,2,5,1,3] 返回值：[1,3,5] 备注：二叉树每个节点的值在区间[1,10000]内，且保证每个节点的值互不相同。
思路：
1 根据前序和后序还原二叉树
2 层序遍历二叉树 保存每层最后一个结点
import java.util.*;
public class Solution {
int[] pre;
HashMap<Integer,Integer> inOrder=new HashMap<Integer,Integer>();
public int[] solve (int[] xianxu, int[] zhongxu) {
TreeNode root=reConstructBinaryTree(xianxu, zhongxu);
ArrayList<Integer> res=new ArrayList<>();
Queue<TreeNode> stack=new LinkedList<TreeNode>();
stack.offer(root);
while(!stack.isEmpty()){
int n=stack.size();
for(int i=0;i<n;i++){
TreeNode temp=stack.poll();
if(i==(n-1)) res.add(temp.val);
if(temp.left!=null) stack.offer(temp.left);
if(temp.right!=null) stack.offer(temp.right);
}
}
int[] resArray=new int[res.size()];
for(int i=0;i<res.size();i++){
resArray[i]=res.get(i);
}
return resArray;
}
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
this.pre=pre;
for(int i=0;i<vin.length;i++) inOrder.put(vin[i],i);
return reBuild(0,0,vin.length-1);
}
public TreeNode reBuild(int preindex,int left,int right){
if(left>right) return null;
TreeNode root=new TreeNode(pre[preindex]);
root.left=reBuild(preindex+1,left,inOrder.get(pre[preindex])-1);
root.right=reBuild(preindex+inOrder.get(pre[preindex])-left+1,inOrder.get(pre[preindex])+1,right);
return root;
}
}
版权声明：本文为qq_34329430原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。