代码随想三刷二叉树篇3

404. 左叶子之和

题目

链接

代码

/*** 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 {public int sumOfLeftLeaves(TreeNode root) {traverse(root,false);return sum;}int sum = 0;public void traverse(TreeNode root,boolean isLeft){if(root==null){return;}if(root.left==null&&root.right==null&&isLeft){sum+=root.val;return;}traverse(root.left,true);traverse(root.right,false);}
}

513. 找树左下角的值

题目

链接

代码

/*** 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 {public int findBottomLeftValue(TreeNode root) {Deque<TreeNode> queue = new LinkedList();queue.add(root);int result = root.val;while(!queue.isEmpty()){int size = queue.size();for(int i =0;i<size;i++){TreeNode temp = queue.removeFirst();if(i==0){result = temp.val;}if(temp.left!=null){queue.addLast(temp.left);}if(temp.right!=null){queue.addLast(temp.right);}}}return result;}
}

112. 路径总和

题目

链接

代码

/*** 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 {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) {return false;}sum += root.val;traverse(root, targetSum);return isHas;}boolean isHas = false;int sum = 0;public void traverse(TreeNode root, int targetSum) {if (isHas) {return;}if (root == null) {return;}if (root.left == null && root.right == null) {if (targetSum == sum) {isHas = true;return;}}if (root.left != null) {sum += root.left.val;traverse(root.left, targetSum);sum -= root.left.val;}if (root.right != null) {sum += root.right.val;traverse(root.right, targetSum);sum -= root.right.val;}}
}

106. 从中序与后序遍历序列构造二叉树

题目

链接

代码

/*** 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 {public TreeNode buildTree(int[] inorder, int[] postorder) {if(inorder==null||inorder.length==0){return null;}if(inorder.length==1){return new TreeNode(inorder[0]);}int val = postorder[postorder.length-1];int index = 0;for(index = 0;index<inorder.length;index++){if(inorder[index]==val){break;}}int[] leftinorder = Arrays.copyOfRange(inorder,0,index);int[] rightinorder = Arrays.copyOfRange(inorder,index+1,inorder.length);int[] leftpostorder = Arrays.copyOfRange(postorder,0,index);int[] rightpostorder = Arrays.copyOfRange(postorder,index,inorder.length-1);TreeNode left = buildTree(leftinorder,leftpostorder);TreeNode right = buildTree(rightinorder,rightpostorder);TreeNode root =new TreeNode(val);root.left = left;root.right = right;return root;}   
}

654. 最大二叉树

题目

链接

代码

/*** 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 {public TreeNode constructMaximumBinaryTree(int[] nums) {return traversal(nums);}public TreeNode traversal(int [] nums){if(nums==null||nums.length==0){return null;}//叶子if(nums.length==1){return  new TreeNode(nums[0]);}//找最大的int max = nums[0];int maxIndex = 0;for(int i=1;i<nums.length;i++){if(max<nums[i]){max = nums[i];maxIndex = i;}}TreeNode t = new TreeNode(max);//分割左右int[] leftNums = Arrays.copyOfRange(nums,0,maxIndex);int[] rightNums = Arrays.copyOfRange(nums,maxIndex+1,nums.length);t.left = traversal(leftNums);t.right = traversal(rightNums);return t;}
}