wordpress4性能,防疫优化措施,免费seo排名软件,软件开发公司的组织架构代码随想录day16| 找树左下角的值 、 路径总和 、 从中序与后序遍历序列构造二叉树 513找树左下角的值层序遍历法递归法 路径总和112. 路径总和113. 路径总和 II 从中序与后序遍历序列构造二叉树思路 513找树左下角的值
层序遍历法 使用层序遍历#xff0c;找到最后一层最左边… 代码随想录day16| 找树左下角的值 、 路径总和 、 从中序与后序遍历序列构造二叉树 513找树左下角的值层序遍历法递归法 路径总和112. 路径总和113. 路径总和 II 从中序与后序遍历序列构造二叉树思路 513找树左下角的值
层序遍历法 使用层序遍历找到最后一层最左边的数值每层循环的第一个值返回即可 class Solution {public int findBottomLeftValue(TreeNode root) {int res 0;QueueTreeNode queue new LinkedList();queue.offer(root);while(!queue.isEmpty()){int size queue.size();for(int i 0 ; i size ; i){TreeNode node queue.poll();if(i 0){res node.val;}if(node.left! null){queue.offer(node.left);}if(node.right ! null){queue.offer(node.right);}}} return res;}}递归法
使用递归遍历二叉树并且记录当前深度到根节点时更新最大深度的值然后使用回溯来更新其他路径时的深度
class Solution {int maxDeepth -1;int res 0;public int findBottomLeftValue(TreeNode root) {int deepth 0;getdeepthleft(root, deepth);return res;}public void getdeepthleft(TreeNode root, int deepth){if(root.left null root.right null){if(deepth maxDeepth){maxDeepth deepth;res root.val;return ;}return ;}if(root.left ! null){deepth 1;getdeepthleft(root.left, deepth);deepth - 1;}if(root.right ! null){deepth 1;getdeepthleft(root.right, deepth);deepth - 1;}}
}路径总和
112. 路径总和 使用递归加回溯找出是否有符合目标的路径 class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root null){return false;}int sum 0;return getPath(root, sum, targetSum);}public boolean getPath(TreeNode root, int sum, int targetSum){if(root.left null root.right null){if(targetSum sum root.val){return true;}return false;}sum root.val;boolean left false;boolean right false;if(root.left ! null){left getPath(root.left, sum, targetSum);}if(root.right ! null){right getPath(root.right, sum, targetSum);}if(left || right){return true; }else{sum - root.val;return false;}}
}113. 路径总和 II 这里相比上一个题目需要收集具体的符合目标的路径所以回溯两个值当前路径值的和sum 、当前收集的路径节点path class Solution {ListInteger path new ArrayList();ListListInteger paths new ArrayList();public ListListInteger pathSum(TreeNode root, int targetSum) {if(root null){return paths;}int sum 0;getPath(root, sum, targetSum);return paths;}public void getPath(TreeNode root, int sum, int targetSum){path.add(root.val);sum root.val;if(root.left null root.right null){if(targetSum sum){//这里注意新创建一个列表不能直接存原列表因为原列表后序会修改paths.add(new ArrayList(path));}return ;}if(root.left ! null){getPath(root.left, sum, targetSum);path.remove(path.size()-1);}if(root.right ! null){getPath(root.right, sum, targetSum);path.remove(path.size()-1);}}}从中序与后序遍历序列构造二叉树
思路
具体思路 注意切割数组时的边界处理 class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {return getTree(inorder, postorder);}public TreeNode getTree(int[] inorder, int[] postorder) {if(inorder null || postorder null){return null;}int val postorder[postorder.length-1];TreeNode root new TreeNode(val);if(inorder.length 1){return root;}int i 0;for(;i inorder.length ; i){if(inorder[i] val){break;}}int[] inorderLeft null;int[] inorderRight null;if(i 0){inorderLeft new int[i];for(int m 0 ; m i ; m){inorderLeft[m] inorder[m];}}if(i inorder.length-1){inorderRight new int[inorder.length-i-1];int n 0;for(int m i1 ; m inorder.length ; m){inorderRight[n] inorder[m];}}int j 0;int[] postorderLeft null;int[] postorderRight null;if(inorderLeft ! null){postorderLeft new int[inorderLeft.length];for(int m 0 ; m inorderLeft.length ; m){postorderLeft[m] postorder[m];}}if(inorderRight!null){postorderRight new int[inorderRight.length];int n 0;int m 0;if(inorderLeft ! null){m inorderLeft.length;}for(; m postorder.length-1 ; m){postorderRight[n] postorder[m];System.out.print(postorderRight[n] );n;}}root.left getTree(inorderLeft, postorderLeft);root.right getTree(inorderRight, postorderRight);return root;}}
