求二叉树是否相同?
用递归法 ,传入左右两棵树的根节点 ,然后比较 left.left == right.left; 以及 left.right ==right.right;
这是递归里面的内容
递归结束的条件:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if( p == null && q == null){ return true ; }else if ( p != null && q == null){ return false; }else if( p == null && q != null ){ return false; }else if (p.val != q.val){ return false; }else{
boolean b1 = isSameTree(p.left , q.left); boolean b2 = isSameTree(p.right ,q.right); boolean b = b1 && b2; return b; } } }
|
求二叉树是否对称 ?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public boolean isSymmetric(TreeNode root) { if(root == null){ return true; }else{ return isTrue(root.left , root.right); } } public boolean isTrue(TreeNode left, TreeNode right){ if(left == null && right == null){ return true; }else if(left == null || right == null){ return false; }else if(left.val != right.val ){ return false; } else{ return isTrue(left.left,right.right) && isTrue(left.right , right.left); } } }
|
求完全二叉树的节点数
方法一 : 最原始的方法, 用迭代法或者递归的方法将二叉树遍历完,得出节点的数量
方法二 : 只针对完全二叉树的解法
在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h-1) 个节点。
按照这个完全二叉树的特征。我们就可以确定一个终止条件
1 2 3
| if(leftDepth == rightDepth){ return 2<<leftDepth - 1; }
|
完全二叉树只有两种情况
情况一:就是满二叉树,情况二:最后一层叶子节点没有满。
- 对于情况一,可以直接用 2^树深度 - 1 来计算,注意这里根节点深度为1。
- 对于情况二,分别递归左孩子,和右孩子,递归到某一深度一定会有左孩子或者右孩子为满二叉树,然后依然可以按照情况1来 计算。
所以说如果整棵树不是满二叉树的话,那么就递归他的左右孩子,直到递归到某棵子树 ,它(子树)是满二叉树, 那么就达到递归截至的条件 ,输出节点数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class Solution { public int countNodes(TreeNode root) { if(root == null){ return 0; } TreeNode leftD = root.left; TreeNode rightD = root.right; int rD = 0; int lD = 0;
while(leftD != null){ leftD = leftD.left; lD++; } while(rightD != null){ rightD = rightD.right; rD++; } if(rD == lD){ return (2 << lD) - 1; }
lNum = countNodes(root.left); rNum = countNodes(root.right); return lNum + rNum + 1; } }
|
总结 :对于这个二叉树来说,他没有遍历所有的节点,如果说一个节点的子树他是满二叉树,那么就只需要用2 << n - 1这个公式就能算出这个子树的所有节点。
平衡二叉树
一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
- 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数。
求解高度用后序遍历 , 求解深度用前序遍历
【因为后序是根据左右孩子的高度,然后父节点再根据左右孩子节点的情况进行 + 1 ===》》》层层向上返回 】
【前序求解的深度 ,顺序是 [中左右]一直向下遍历,不向上返回结果。符合一直向下统计节点的深度 】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| class Solution { public boolean isBalanced(TreeNode root) { int res = isTree(root); return res == -1 ? false : true; } public int isTree(TreeNode node){ if(node == null){ return 0; } int ll = isTree(node.left); if(ll == -1){ return -1; } int rl = isTree(node.right); if(rl == -1){ return -1; } if(Math.abs(ll-rl) > 1){ return -1; } return Math.max(ll,rl) + 1; } }
|
求解深度的方法(c++ 实现)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { public: int result; void getDepth(TreeNode* node, int depth) { result = depth > result ? depth : result;
if (node->left == NULL && node->right == NULL) return ;
if (node->left) { depth++; getDepth(node->left, depth); depth--; } if (node->right) { depth++; getDepth(node->right, depth); depth--; } return ; } int maxDepth(TreeNode* root) { result = 0; if (root == 0) return result; getDepth(root, 1); return result; } };
|
二叉树的所有路径
给定一个二叉树,返回所有从根节点到叶子节点的路径。
在这道题目中将第一次涉及到回溯,因为我们要把路径记录下来,需要回溯来回退一个路径再进入另一个路径。
求二叉树的所有路径思路(草图)
- 创建路径集合path 以及 结果集合list。用于存储路径与最后的结果
- 前序遍历 ,先将父节点加入到路径集合path中
- 递归结束的条件 –> 到叶子节点 (如图的 4 号节点)
- 递归结束,回溯之前。将该路径保存到结果路径中
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> list = new ArrayList<>(); if(root == null){ return list; } List<Integer> path = new ArrayList<>(); prefix(root,path,list); return list; } public void prefix(TreeNode node , List<Integer> path, List<String> list){ path.add(node.val);
if(node.left == null && node.right == null){ StringBuffer sb = new StringBuffer(); for(int i=0 ;i<path.size() - 1 ;i++){ sb.append(path.get(i)).append("->"); }
sb.append(path.get(path.size()-1)); list.add(sb.toString()); return; } if(node.left != null){ prefix(node.left , path ,list); path.remove(path.size() - 1 ); } if(node.right != null){ prefix(node.right , path , list); path.remove(path.size() - 1); } } }
|
获取树最左下角的节点的值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
|
class Solution { public int res = 0; public int depth = - 1; public int findBottomLeftValue(TreeNode root) { if(root == null){ return 0; } GetLeft(root,1); return res; } public void GetLeft(TreeNode root , int deep){ if(root.left == null && root.right == null){ if(deep > depth){ depth = deep; res = root.val; } } if(root.left != null){ GetLeft(root.left , deep+1); } if(root.right != null){ GetLeft(root.right, deep + 1); } } }
*/ class Solution { List<List<Integer>> list = new ArrayList<>(); public int findBottomLeftValue(TreeNode root) { if(root == null){ return 0; } Queue<TreeNode> que = new LinkedList<>(); que.offer(root); while(!que.isEmpty()){ int size = que.size(); List<Integer> nodeList = new ArrayList<>(); for(int i= 0 ;i<size;i++){ TreeNode node = que.poll(); nodeList.add(node.val); if(node.left != null){ que.offer(node.left); } if(node.right != null){ que.offer(node.right); } } list.add(nodeList); } return list.get(list.size()- 1).get(0); } }
class Solution {
public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int res = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode poll = queue.poll(); if (i == 0) { res = poll.val; } if (poll.left != null) { queue.offer(poll.left); } if (poll.right != null) { queue.offer(poll.right); } } } return res; } }
|
路径总和二
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]
示例 2:
输入:root = [1,2,3], targetSum = 5
输出:[]
示例 3:
输入:root = [1,2], targetSum = 0
输出:[]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| class Solution { List<List<Integer>> list = new ArrayList<>(); public List<List<Integer>> pathSum(TreeNode root, int targetSum) { if(root== null){ return list; } List<Integer> path = new ArrayList<>(); prefix(root,path,targetSum); return list; } public void prefix(TreeNode root, List<Integer> path,int targetSum){ path.add(root.val); if(root.left == null && root.right == null){ List<Integer> alist= new ArrayList<>(); for(int i= 0;i<path.size();i++){ alist.add(path.get(i)); } int size = alist.size(); int sum = 0; for(int j =0;j<size;j++){ sum += alist.get(j); } if(sum == targetSum){ list.add(alist); } } if(root.left != null){ prefix(root.left , path, targetSum); path.remove(path.size()-1); } if(root.right != null){ prefix(root.right , path, targetSum); path.remove(path.size()-1); } } }
|
从中序与后序构建二叉树
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
示例 1:
输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]输出:[3,9,20,null,null,15,7]示例 2:
输入:inorder = [-1], postorder = [-1]输出:[-1]
思路
- 判断数组是否为空 !
- 不为空则向下继续,为空返回null
- 去后序数组中的最后一个元素为树的头节点的val值,(原因由后序遍历可知)
- 切割中序数组 ,以头节点的val值为区分(作为切割点) ,切割成中序左数组 和 中序右数组
- 切割后序数组, 切成后序左数组 和后序右数组
- 递归处理左右区间
思维图
代码实现(复杂易懂)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if(inorder.length == 0 || postorder.length == 0){ return null; } int rootVal = postorder[postorder.length - 1]; TreeNode node = new TreeNode(rootVal); int inSize = inorder.length; int postSize = postorder.length; int mid; for(mid = 0; mid < inSize;mid++){ if(inorder[mid] == rootVal){ break; } } //切割中序 int inBegin = 0; int inEnd = mid; int[] newIn = Arrays.copyOfRange(inorder,inBegin,inEnd); int[] newPost = Arrays.copyOfRange(postorder,inBegin,inEnd); node.left = buildTree(newIn,newPost);
int postBegin = mid + 1 ; int postEnd = postorder.length - 1; int[] newIn2 = Arrays.copyOfRange(inorder , postBegin , inSize); int[] newPost2 = Arrays.copyOfRange(postorder,mid, postEnd); node.right = buildTree(newIn2,newPost2); return node; } }
|
代码实现(简易map版)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { Map<Integer, Integer> map; // 方便根据数值查找位置 public TreeNode buildTree(int[] inorder, int[] postorder) { map = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置 map.put(inorder[i], i); }
return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开 } public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) { // 参数里的范围都是前闭后开 if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开,说明没有元素,返回空树 return null; } int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置 TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点 int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数,用来确定后序数列的个数 root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft); root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);
return root; } }
|
从前序与中序构建二叉树
思路
与从中序和后序构建二叉树相同
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { Map<Integer, Integer> map; // 方便根据数值查找位置 public TreeNode buildTree(int[] inorder, int[] postorder) { map = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置 map.put(inorder[i], i); }
return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开 } public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) { // 参数里的范围都是前闭后开 if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开,说明没有元素,返回空树 return null; } int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置 TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点 int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数,用来确定后序数列的个数 root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft); root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);
return root; } }
|
参考说明(感谢!):
力扣!
代码随想录!