Directory
?LeetCode513. Find the value in the lower left corner of the tree?
?LeetCode112. Path sum?
?LeetCode113. Path Sum ||?
?LeetCode106. Construct a binary tree from inorder and postorder traversal sequences?
?LeetCode105. Construct a binary tree from preorder and inorder traversal?
?LeetCode513. Find the value in the lower left corner of the tree?
Link: 513. Find the value in the lower left corner of the tree
Given the root
rootof a binary tree, find the value of the bottommost leftmost node of the binary tree.Assume there is at least one node in the binary tree.
My idea is to traverse the layers directly, and then return the first element of the last layer. The code is as follows:
public int findBottomLeftValue(TreeNode root) {
// The range of the number of nodes in the binary tree is [1,104]
Queue<TreeNode> qu=new LinkedList<>();
List<List<Integer>> result=new ArrayList<>();
qu.offer(root);
while(!qu.isEmpty()){
int size=qu. size();
List<Integer> list=new ArrayList<>();
while(size>0){
TreeNode node=qu.poll();
list. add(node. val);
if(node. left!=null){
qu.offer(node.left);
}
if(node.right!=null){
qu.offer(node.right);
}
size--;
}
result. add(list);
}
return result.get(result.size()-1).get(0);
}
?LeetCode112. Path sum?
Links: 112. Path Sum
You are given the root node of the binary tree
rootand an integertargetSumrepresenting the target sum. Determine whether there is a path from root node to leaf node in the tree, and the sum of all node values on this path is equal to the target andtargetSum. If present, returntrue; otherwise, returnfalse.Leaf node refers to a node without child nodes.
The typical backtracking method for the path problem, the code is as follows:
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) {
return false;
}
targetSum-=root.val;
return traversal(root, targetSum);
}
// backtrack
public boolean traversal(TreeNode root, int targetSum){
if(root.left==null & amp; & amp; root.right==null & amp; & amp; targetSum==0){
return true;
}
if(root.left==null & amp; & amp; root.right==null){
return false;
}
if(root. left!=null){
targetSum-=root.left.val;
if(traversal(root. left, targetSum)){
return true;
}
targetSum + =root.left.val;
}
if(root. right!=null){
targetSum-=root.right.val;
if(traversal(root.right,targetSum)){
return true;
}
targetSum + =root.right.val;
}
return false;
}
?LeetCode113. Path sum||?
link: 113. path sum ||
Given the root node
rootof your binary tree and an integer target andtargetSum, find all root to leaf paths whose sum is equal to the given target and path.Leaf node refers to a node without child nodes.
Or the backtracking method, the essence of the backtracking method is to subtract, then recurse, and then add back, the code is as follows:
List<List<Integer>> result;
List<Integer> path;
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
result=new ArrayList<>();
path=new ArrayList<>();
if(root==null){
return result;
}
targetSum-=root.val;
path. add(root. val);
traversal(root, targetSum);
return result;
}
public void traversal(TreeNode root,int targetSum){
if(root.left==null & amp; & amp; root.right==null & amp; & amp; targetSum==0){
result. add(new ArrayList(path));
return;
}
if(root. left!=null){
targetSum-=root.left.val;
path.add(root.left.val);
traversal(root. left, targetSum);
path. remove(path. size()-1);
targetSum + =root.left.val;
}
if(root. right!=null){
path.add(root.right.val);
targetSum-=root.right.val;
traversal(root.right, targetSum);
path. remove(path. size()-1);
targetSum + =root.right.val;
}
}
?LeetCode106. Construct a binary tree from inorder and postorder traversal sequences?
Link: 106. Construct a binary tree from inorder and postorder traversal sequences
Given two integer arrays
inorderandpostorder, whereinorderis the inorder traversal of a binary tree andpostorderis the same The post-order traversal of a tree, please construct and return this binary tree.
You need to know the order of in-order traversal and post-order traversal, and then construct it yourself on paper, and write the code according to your own ideas. The point to pay attention to is to maintain consistency when dividing the array, either left-closed and right-closed, or Close left and open right, the code is as follows:
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length==0 || postorder.length==0){
return null;
}
return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
}
public TreeNode build(int[] inorder,int in_start,int in_end,int[] postorder,int post_start,int post_end){
if (in_start > in_end || post_start > post_end) {
return null;
}
TreeNode root=new TreeNode(postorder[post_end]);
int index=0;
for(int i=in_start;i<=in_end;i ++ ){
if(inorder[i]==postorder[post_end]){
index=i;
break;
}
}
int leftLen=index-in_start;
root.left=build(inorder,in_start,in_start + leftLen-1,postorder,post_start,post_start + leftLen-1);
root.right=build(inorder,in_start + leftLen + 1,in_end,postorder,post_start + leftLen,post_end-1);
return root;
}
?LeetCode105. Construct a binary tree from preorder and inorder traversal?
Link: 105. Construct a Binary Tree from Inorder and Preorder Traversal Sequences
Given two integer arrays
preorderandinorder, wherepreorderis the preorder traversal of a binary tree,inorderis the inorder traversal of the same tree, please construct a binary tree and return its root node.
If you can use inorder and postorder to construct a binary tree, then the preorder and inorder are the same, the code is as follows:
public TreeNode buildTree(int[] preorder, int[] inorder) {
return bulid(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public TreeNode bulid(int[] preorder,int pre_start,int pre_end,int[] inorder,int in_start,int in_end){
if(in_start>in_end || pre_start>pre_end){
return null;
}
TreeNode root=new TreeNode(preorder[pre_start]);
int index=0;
for(int i=in_start;i<=in_end;i ++ ){
if(inorder[i]==preorder[pre_start]){
index=i;
break;
}
}
int leftLen=index-in_start;
root.left=bulid(preorder,pre_start + 1,pre_start + leftLen,inorder,in_start,in_start + leftLen-1);
root.right=bulid(preorder,pre_start + leftLen + 1,pre_end,inorder,in_start + leftLen + 1,in_end);
return root;
}