/** * 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 invertTree(TreeNode root) { if (root == null) { return root; } Queue<TreeNode> que = new LinkedList<>(); que.offer(root); while (!que.isEmpty()) { int len = que.size(); while (len > 0) { TreeNode tmp = que.poll(); TreeNode tmpSon = tmp.left; tmp.left = tmp.right; tmp.right = tmpSon; if (tmp.left != null) { que.offer(tmp.left); } if (tmp.right != null) { que.offer(tmp.right); } len--; } } return root; } }
Interview-Notes
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { // 递归 // 递归检查左子树 是否包含节点 p 或 q。 // 递归检查右子树 是否包含节点 p 或 q。 // 如果当前节点自身是 p 或 q 中的一个，且其左子树或右子树包含另一个节点，那么该节点就是最近的公共祖先。 // 如果当前节点的左右子树各包含一个目标节点（p 和 q），那么当前节点就是最近的公共祖先。 // 如果上述情况都不成立，返回找到的包含目标节点的子树（可能为空，表示当前子树不包含目标节点）。 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 && right == null) { //一边为空，一边不为空，说明在公共祖先在不为空的一边 return left; }else if (left == null && right != null) { return right; } return null; } }
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ // 一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构 // 序列化，层序遍历。反序列化，去除首尾"[]"，将字符串按照","划分，采用层序遍历的方式，还原树 // 层序遍历 public class Codec { // 序列化，层序遍历树。需要注意的是：在结尾删除"," public String serialize(TreeNode root) { if (root == null) { return "[]"; } Queue<TreeNode> que = new LinkedList<>(); StringBuffer sb = new StringBuffer(); sb.append("["); que.offer(root); while (!que.isEmpty()) { TreeNode tmp = que.poll(); if (tmp != null) { que.offer(tmp.left); que.offer(tmp.right); // 这里最终的结果会多出几个null值，对于序列化二叉树没有任何影响 sb.append(tmp.val + ","); } else { sb.append("null,"); } } sb.deleteCharAt(sb.length() - 1); sb.append("]"); return sb.toString(); } // Decodes your encoded data to tree. // 用split方法划分，将字符串划分为一个字符串数组 // 字符串转为Integer的方法 Integer.parseInt(); public TreeNode deserialize(String data) { if (data.equals("[]")) { return null; } String[] val = data.substring(1, data.length() - 1).split(","); TreeNode root = new TreeNode(Integer.parseInt(val[0])); Queue<TreeNode> que = new LinkedList<>(); que.offer(root); int i = 1; while (!que.isEmpty()) { TreeNode tmp = que.poll(); if (!val[i].equals("null")) { tmp.left = new TreeNode(Integer.parseInt(val[i])); que.offer(tmp.left); } i++; if (!val[i].equals("null")) { tmp.right = new TreeNode(Integer.parseInt(val[i])); que.offer(tmp.right); } i++; } return root; } } // Your Codec object will be instantiated and called as such: // Codec ser = new Codec(); // Codec deser = new Codec(); // TreeNode ans = deser.deserialize(ser.serialize(root));
/** * 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 { //计算所有路径和为targetSym的路径：深度优先搜索 //定义函数rootSum 用来计算以某个节点为起点时的路径和为targetSum的条数 //pathSum函数递归调用自身，遍历所有节点； // 时间复杂度O(N^2),空间复杂度(N) // 采用前缀和的方式，时间复杂度O(N),空间复杂度O(N) // 采用先序遍历的方式用hashmap记录所有路径和，若遍历当前节点时，hashmap中存在路径和-targetsum // 说明此路径中存在某个节点到当前节点的路径和为target // 最后需要回溯，防止影响到其他节点 public int pathSum(TreeNode root, long targetSum) { // taegetSum 会溢出，需要改为long Map<Long, Integer> prefix = new HashMap<>(); prefix.put(0L, 1); // 为了处理路径和刚好等于targetSum的特殊情况 return dfs(root, prefix, 0, targetSum); } public int dfs(TreeNode node, Map<Long, Integer> prefix, long curr,long targetSum) { if (node == null) { return 0; } int count = 0; curr += node.val; count = prefix.getOrDefault(curr - targetSum, 0); prefix.put(curr, prefix.getOrDefault(curr, 0) + 1); count += dfs(node.left, prefix, curr, targetSum); count += dfs(node.right, prefix, curr, targetSum); prefix.put(curr, prefix.get(curr) - 1); // 递归返回后，减少技术，防止影响其他路径的搜索 return count; } }
/** * 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 { // 解决方案使用了一个递归的方法。算法的关键步骤如下: // 如果当前节点为空,则返回 null。 // 首先递归处理右子树,因为我们需要先处理比当前节点大的节点。 // 处理完右子树后,累加当前节点的值到 sum 变量中,并将当前节点的值更新为 sum。 // 最后递归处理左子树 int sum = 0; public TreeNode convertBST(TreeNode root) { if (root == null) { return null; } convertBST(root.right); sum += root.val; root.val = sum; convertBST(root.left); return root; } }
/** * 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 { //对每一个节点求左子树的最大深度 + 右子树的最大深度 // 他们之和的最大值即为直径。 // 直径为所有子节点的最大 int sum = 0; public int diameterOfBinaryTree(TreeNode root) { maxDepth(root); return sum; } public int maxDepth(TreeNode node) { if (node == null) { return 0; } int leftDepth = maxDepth(node.left); int rightDepth = maxDepth(node.right); sum = Math.max(sum, leftDepth + rightDepth); return Math.max(leftDepth, rightDepth) + 1; //左右节点的最大深度 + 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 { //层序遍历 两棵树的对应位置都不为空则值相加 //以返回第一颗数为例，如果第一颗树和第二颗数对应位置都不为空，值相加；第一颗树为空，第二颗不空，让第一颗的对应的位置指向第二颗的 //对应位置；第二颗为空，第一颗为空，不操作； public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) { return root2; } if (root2 == null) { return root1; } Queue<TreeNode> que = new LinkedList<>(); que.offer(root1); que.offer(root2); while (!que.isEmpty()) { TreeNode tmp1 = que.poll(); TreeNode tmp2 = que.poll(); tmp1.val += tmp2.val; if (tmp1.left != null && tmp2.left != null) { que.offer(tmp1.left); // 层序遍历，每次poll两棵树对应位置的两个点 que.offer(tmp2.left); } else if (tmp1.left == null && tmp2.left != null) { tmp1.left = tmp2.left; } if (tmp1.right != null && tmp2.right != null) { que.offer(tmp1.right); que.offer(tmp2.right); } else if (tmp1.right == null && tmp2.right != null) { tmp1.right = tmp2.right; } } return root1; } }
/** * 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; * } * } */ // 两种方法 ： 1. 递归 2.迭代 class Solution { List<Integer> res; public List<Integer> inorderTraversal(TreeNode root) { res = new ArrayList<>(); Stack<TreeNode> stack = new Stack(); TreeNode cur = root; while (!stack.isEmpty() || cur != null) { while (cur != null) { stack.push(cur); cur = cur.left; // 左 } cur = stack.pop(); res.add(cur.val); // 中 cur = cur.right; // 右 } return res; } }
class Solution { public int numTrees(int n) { int[] dp = new int[n+1]; //dp[i]表示n个节点组成的二叉搜索数的种数 dp[1] = 1; dp[0] = 1; //递推公式：选定任意点i作为根节点，则左子树为[1,i-1];右子树为[i+1,n]; //dp[i] = ∑(dp[i-1] * dp[n-i]) // dp[1] = 1 // 遍历顺序：从前向后 for (int i = 2; i <=n; i++) { // 总共有多少个节点 for (int j = 1; j <= i; j++) { // 选哪一个做根节点 dp[i] += dp[j-1]*dp[i-j]; } } return dp[n]; } }
/** * 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 isValidBST(TreeNode root) { long max = Long.MAX_VALUE; long min = Long.MIN_VALUE; return isValid(root, min, max); } // Deque<TreeNode> stack = new LinkedList<>(); // long inorder = Long.MIN_VALUE; // while (!stack.isEmpty() || root != null) { // while (root != null) { // stack.push(root); // root = root.left; // } // TreeNode tmp = stack.pop(); // if ((long)tmp.val <= inorder) { // return false; // } // root = tmp.right; // inorder = tmp.val; // } // return true; // } public boolean isValid(TreeNode node, long min, long max) { if (node == null) { return true; } if (node.val <= min || node.val >= max) { return false; } return isValid(node.left, min, node.val) && isValid(node.right, node.val, max); } }