今日任务
- 513.找树左下角的值
- 112. 路径总和
- 113.路径总和ii
- 106.从中序与后序遍历序列构造二叉树
- 105.从前序与中序遍历序列构造二叉树
- 100.相同的树
- 572.另一个树的子树
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 ans = 0;
public int findBottomLeftValue(TreeNode root) {
research(root);
return ans;
}
public void research(TreeNode root){
if(root == null) return;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
while(!que.isEmpty()){
int n = que.size();
ans = que.peek().val;
while(n > 0){
TreeNode temp = que.poll();
if(temp.left != null) que.offer(temp.left);
if(temp.right != null) que.offer(temp.right);
n--;
}
}
}
}
递归
一直往下寻找，返回层数和数值
class Solution {
public:
int maxDepth = INT_MIN;
int result;
void traversal(TreeNode* root, int depth) {
if (root->left == NULL && root->right == NULL) {
if (depth > maxDepth) {
maxDepth = depth;
result = root->val;
}
return;
}
if (root->left) {
traversal(root->left, depth + 1); // 隐藏着回溯
}
if (root->right) {
traversal(root->right, depth + 1); // 隐藏着回溯
}
return;
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);
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 flag = false;
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
search(root, 0, targetSum);
return flag;
}
public void search(TreeNode node, int sums, int target){
if (flag) return;
sums += node.val;
if(node.left == null && node.right == null){
if(sums == target) flag = true;
return;
}
if (node.left != null) search(node.left, sums, target);
if (node.right != null) search(node.right, sums, target);
}
}
113. 路径总和ii
这题需要注意java如何copy数值而不是传递地址，
ans.add(new ArrayList<Integer>(list))
/**
* 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 List<List<Integer>> ans = new ArrayList<List<Integer>>();
public int target = 0;
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) return ans;
target = targetSum;
Stack<Integer> list = new Stack<Integer>();
search(root, 0, list);
return ans;
}
public void search(TreeNode node, int sums, Stack<Integer> list){
sums += node.val;
list.push(node.val);
if(node.left == null && node.right == null){
if (sums == target) ans.add(new ArrayList<Integer>(list));
}
else{
if(node.left != null) search(node.left, sums, list);
if(node.right != null) search(node.right, sums, list);
}
list.pop();
return;
}
}
106.从中序与后序遍历序列构造二叉树
注意我们的java的数组不能直接取某一段的数值，所以我们只能整个数组传递。因此，我们需要计算左右子树的大小，从而确定左右指针。
这里的话我们直接返回node即可
这里的java知识点还有Map的应用
定义
Map<Integer, Integer> map;
map = new HashMap<>();
map.put(inorder[i], i)
map.get(postorder[postEnd - 1])
/**
* 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 {
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;
}
}
105.从前序与中序遍历序列构造二叉树
/**
* 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 {
Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for(int i = 0; i < preorder.length; i++) map.put(inorder[i], i);
return building(preorder, inorder, 0, preorder.length, 0, inorder.length);
}
public TreeNode building(int[] preorder, int[] inorder, int prestart, int preend, int instart, int inend){
if(prestart >= preend || instart >= inend){
return null;
}
int rootIndex = map.get(preorder[prestart]);
TreeNode temp = new TreeNode(inorder[rootIndex]);
int leftLen = rootIndex - instart;
temp.left = building(preorder, inorder, prestart+1, prestart+1+leftLen, instart, rootIndex);
temp.right = building(preorder, inorder, prestart+1+leftLen, preend, rootIndex + 1, inend);
return temp;
}
}
复习如何对比两个树，利用递归的方式
100.两棵树对比
/**
* 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 isSameTree(TreeNode p, TreeNode q) {
if(p == null && q != null) return false;
if(p != null && q == null) return false;
if(p == null && q == null) return true;
if(p.val != q.val) return false;
return (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
}
}
572.
/**
* 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 isSubtree(TreeNode root, TreeNode subRoot) {
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
while(!que.isEmpty()){
int n = que.size();
while(n > 0){
TreeNode temp = que.poll();
if (temp.val == subRoot.val){
if(compare(temp, subRoot)) return true;
}
if(temp.left != null) que.offer(temp.left);
if(temp.right != null) que.offer(temp.right);
n--;
}
}
return false;
}
public boolean compare(TreeNode p, TreeNode q){
if(p == null && q != null) return false;
if(q == null && p != null) return false;
if(p == null && q == null) return true;
if(p.val != q.val) return false;
return (compare(p.left, q.left)) && (compare(p.right, q.right));
}
}
标签：right,TreeNode,val,int,随想录,Day17,二叉树,return,left From： https://www.cnblogs.com/fangleSea/p/17459193.html