菜鸡的原地踏步史02(◐‿◑)

每日一念
改掉自己想到哪写哪的坏习惯

二叉树

二叉树的中序遍历

class Solution {/**中序遍历左 - 中 - 右*/private List<Integer> res =  new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {if(root == null) {return res;}tranverse(root);return res;}public void tranverse(TreeNode node) {if(node == null) {return;}tranverse(node.left);res.add(node.val);tranverse(node.right);}
}

二叉树的最大深度

class Solution {/**比较左右子树深度，取最大值，还要加上root的1*/int max = 0;public int maxDepth(TreeNode root) {if(root == null) {return 0;}return tranverse(root);}public int tranverse(TreeNode node) {if(node == null) {return 0;}int left = tranverse(node.left);int right = tranverse(node.right);max = Math.max(left, right) + 1;return max;} 
}

翻转二叉树

class Solution {/**递归的每一层在干什么在交换结点*/public TreeNode invertTree(TreeNode root) {tranverse(root);return root;}public void tranverse(TreeNode node) {if(node == null) {return;}TreeNode temp = null;temp = node.left;node.left = node.right;node.right = temp;tranverse(node.left);tranverse(node.right);}
}

对称二叉树

class Solution {/**每一层在干什么？判断左子树结点和右子树结点是否值相同*/public boolean isSymmetric(TreeNode root) {if(root == null) {return true;}return tranverse(root.left, root.right);}public boolean tranverse(TreeNode left, TreeNode right) {if(left == null && right != null) {return false;}if(left != null && right == null) {return false;}if(left == null && right == null) {return true;}if(left.val != right.val) {return false;}boolean l = tranverse(left.left, right.right);boolean r = tranverse(left.right, right.left);return l && r;}}

二叉树的直径

class Solution {/***/int maxlen = 0;public int diameterOfBinaryTree(TreeNode root) {tranverse(root);return maxlen;}public int tranverse(TreeNode root) {if(root == null) {return 0;}int left = tranverse(root.left);int right = tranverse(root.right);maxlen = Math.max(left + right, maxlen);return Math.max(left, right) + 1;}
}

二叉树的层序遍历

class Solution {/**每一层保存root结点的值*/List<List<Integer>> res = new ArrayList();public List<List<Integer>> levelOrder(TreeNode root) {if(root == null) {return res;}tranverse(root, 0);return res;}public void tranverse(TreeNode root, int depth) {if(root == null) {return;}if(res.size() <= depth) {res.add(new ArrayList<>());}res.get(depth).add(root.val);tranverse(root.left, depth + 1);tranverse(root.right, depth + 1);}
}

将有序数组转化为二叉搜索树

class Solution {/**每一层要做什么提取目前nums的根节点，建立左右子树*/public TreeNode sortedArrayToBST(int[] nums) {if(nums == null || nums.length == 0) {return null;}return tranverse(nums, 0, nums.length - 1);}public TreeNode tranverse(int[] nums, int start, int end) {if(start > end) {return null;}int mid = (start + end) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = tranverse(nums, start, mid - 1);root.right = tranverse(nums, mid + 1, end);return root;}
}

验证二叉搜索树

class Solution {/**每层在做什么可以类比前面将nums分段的，这题是在比较root.val和min、max*/public boolean isValidBST(TreeNode root) {return tranverse(root, null, null);}public boolean tranverse(TreeNode root, Integer min, Integer max) {if(root == null) {return true;}if((min != null && root.val <= min) || (max != null && root.val >= max)) {return false;}boolean left = tranverse(root.left, min, root.val);boolean right = tranverse(root.right, root.val, max);return left && right;}
}

二叉搜索树中第k小的元素

class Solution {/**简单朴素的想法将所有元素装到list里面，排序后找出第k-1个元素*/List<Integer> list = new ArrayList<>();public int kthSmallest(TreeNode root, int k) {tranverse(root);Collections.sort(list);return list.get(k - 1);}public void tranverse(TreeNode root) {if(root == null) {return;}list.add(root.val);tranverse(root.left);tranverse(root.right);}
}

二叉树的右视图

class Solution {/**每一层在做什么？先右子树depth++，再左子树depth--res.size() < depth时，没存这层的结点值，需要存一下*/List<Integer> res = new ArrayList<>();int depth = 0;public List<Integer> rightSideView(TreeNode root) {tranverse(root);return res;}public void tranverse(TreeNode root) {if(root == null) {return;}depth++;if(res.size() < depth) {res.add(root.val);}tranverse(root.right);tranverse(root.left);depth--;}
}

二叉树展开为链表

class Solution {/**每一层在干什么？将左子树结点移到右子树root.right右子树移到root右子树的最后结点.right2/  \3    42\3    42\3\4*/public void flatten(TreeNode root) {if(root == null) {return;}flatten(root.left);flatten(root.right);TreeNode node_left = root.left;TreeNode node_right = root.right;root.left = null;root.right = node_left;TreeNode newRoot = root;while(newRoot.right != null) {newRoot = newRoot.right;}newRoot.right = node_right;}
}

从前序和中序遍历构造二叉树

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return tranverse(preorder, 0, preorder.length - 1,inorder, 0, inorder.length - 1);}public TreeNode tranverse(int[] preorder, int preStart, int preEnd,int[] inorder, int inStart, int inEnd) {if(preStart > preEnd) {return null;}int rootValue = preorder[preStart];TreeNode root = new TreeNode(rootValue);int rootIndex = 0;for(int i = inStart; i <= inEnd; i++) {if(inorder[i] == rootValue) {rootIndex = i;}}int leftLen = rootIndex - inStart;int rightLen = inEnd - rootIndex;root.left = tranverse(preorder, preStart + 1, preStart + leftLen, inorder, inStart, rootIndex - 1);root.right = tranverse(preorder, preStart + leftLen + 1, preEnd, inorder, rootIndex + 1, inEnd);return root;}
}

路径总和III

class Solution {/**每一层在做什么？dps1到一层的根节点，dps2往下搜寻有没有和=targertSum的需要注意测试用例int转成long类型*/int ans = 0;int target = 0;public int pathSum(TreeNode root, int targetSum) {target = targetSum;dps1(root);return ans;}public void dps1(TreeNode root) {if(root == null) {return;}dps2(root, root.val);dps1(root.left);dps1(root.right);}public void dps2(TreeNode root, long t) {if(t == target) {ans++;}if(root.left != null) {dps2(root.left, root.left.val + t);}if(root.right != null) {dps2(root.right, root.right.val + t);}}
}

二叉树的最近公共祖先

class Solution {/**每一层都在做什么？left记录找到的最近左祖先，right记录找到的最近右祖先left right都有 -- 祖先root只在left -- 返回left只在right -- 返回right都没有 -- 返回null*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q) {return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left != null && right != null) {return root;}else if(left != null) {return left;}else if(right != null) {return right;}else {return null;}}
}

二叉树中最大路径和

class Solution {/**难题直接灵神yyds看了灵神的题解，其实和最大深度差不多（真的 QAQ*/int ans = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dps(root);return ans;}public int dps(TreeNode root) {if(root == null) {return 0;}int leftValue = dps(root.left);int rightValue = dps(root.right);ans = Math.max(ans, leftValue + rightValue + root.val);return Math.max(Math.max(leftValue, rightValue) + root.val, 0);}
}