一、LC94、144、145中序，前序，后续遍历
List<Integer> front = new ArrayList<>(); List<Integer> mid = new ArrayList<>(); List<Integer> back = new ArrayList<>(); //前序遍历 public void Preorder(TreeNode root){ if(root == null) return; front.add(root.val); Preorder(root.left); Preorder(root.right); } //中序遍历 public void Inorder(TreeNode root){ if(root == null) return; Inorder(root.left); mid.add(root.val); Inorder(root.right); } //后序遍历 public void Postorder(TreeNode root){ if(root == null) return; Postorder(root.left); Postorder(root.right); back.add(root.val); }
二、LC104、111 二叉树最大 最小深度
// 最大深度 public int maxDepth(TreeNode root) { if(root == null) return 0; return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1; } // 最小深度 public int minDepth(TreeNode root) { if (root == null){ return 0; }else if (root.left == null || root.right == null){ return 1; }else{ return Math.min(minDepth(root.left),minDepth(root.right)) + 1; } }
三、LC100 是否同一棵树
public boolean isSameTree(TreeNode p, TreeNode q) { if(p==null && q==null){ return true; } if(p!=null && q!=null && p.val==q.val){ return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); } return false; }
四、LC101 是否对称二叉树
public boolean isSymmetric(TreeNode root) { if(root==null) return true; return dfs(root.left,root.right); } public boolean dfs(TreeNode root1,TreeNode root2){ if(root1==null&&root2==null) return true; if(root1==null || root2==null || root1.val != root2.val) return false; return dfs(root1.left,root2.right)&&dfs(root1.right,root2.left); }
五、LC110 判断平衡二叉树
public boolean isBalanced(TreeNode root) { if(root==null) return true; if(Math.abs(maxDepth(root.left) - maxDepth(root.right)) <=1 ){ return isBalanced(root.left)&&isBalanced(root.right); } return false; } private int maxDepth(TreeNode root){ if(root==null) return 0; return Math.max(getHigh(root.left),getHigh(root.right))+1; }
六、LC112 二叉树路径 目标值总和
class Solution { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } if (root.left == null && root.right == null) { return sum == root.val; } return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); } }
七、LC226 翻转二叉树
public static TreeNode invertTree(TreeNode root) { if (root == null || (root.right == null && root.left == null)){ return root; } TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; }
七、判断是否为子树【子树，要么等于，要么等于左/右子树。】
public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (root == null) return false; //子树，要么等于，要么等于左/右子树。 return subFrom(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot); } public boolean subFrom(TreeNode root, TreeNode subRoot){ if (root == null && subRoot == null) return true; if (root == null || subRoot == null) return false; if (root.val != subRoot.val) return false; return subFrom(root.left, subRoot.left) && subFrom(root.right, subRoot.right); }
八、LC589、590 N叉树的前序 后续遍历
// 前序遍历 class Solution { List<Integer> res = new ArrayList<Integer>(); public List<Integer> preorder(Node root) { //递归版 if(root == null) return res; res.add(root.val); for(Node child : root.children) { preorder(child); } return res; } } // 后序遍历 class Solution { List<Integer> res = new ArrayList<Integer>(); public List<Integer> postorder(Node root) { //递归版 if(root == null) return res; for(Node child : root.children) { postorder(child); } res.add(root.val); return res; } }
九、LC559 N叉树的最大深度
public int maxDepth(Node root) { if(root == null) return 0; int max = 0; for(Node node : root.children){ max = Math.max(maxDepth(node),max); } return max + 1; }
十、Offer27 二叉树的镜像
public TreeNode mirrorTree(TreeNode root) { if (root == null)return null; TreeNode tmpNode = root.left; root.left = mirrorTree(root.right); root.right = mirrorTree(tmpNode); return root; }
十一、NC 是否为二叉搜索树和完全二叉树
public boolean[] judgeIt (TreeNode root) { // write code here boolean bst = isBST(root, Long.MIN_VALUE, Long.MAX_VALUE); boolean ct = isCompeteTree(root); return new boolean[]{bst, ct}; } public boolean isBST(TreeNode root, long lower, long upper) { if (null == root) return true; if (root.val <= lower || root.val >= upper) { return false; } return isBST(root.left, lower, root.val) && isBST(root.right, root.val, upper); } public boolean isCompeteTree(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (queue.peek() != null) { TreeNode last = queue.poll(); queue.offer(last.left); queue.offer(last.right); } while (!queue.isEmpty() && queue.peek() == null) { queue.poll(); } return queue.isEmpty(); }
十二、二叉树的最大路径之和
public class MaxPathSumTree { int max =Integer.MIN_VALUE; public int maxPathSum (TreeNode root) { if (root == null) return 0; help(root); return max; } public int help(TreeNode root) { if(root == null) { return 0; } //如果子节点为负数节点 让他的计算值为0 则一个节点的最大值为 root+left + right int left = Math.max(help(root.left), 0); int right = Math.max(help(root.right), 0); max = Math.max(max, root.val + left + right); return Math.max(root.val + left, root.val + right); } }
十三、LC404 求二叉树左叶子之和
public static int sumOfLeftLeaves(TreeNode root) { int sum = 0; if(root == null) return 0; if(root.left != null ){ if(root.left.left == null && root.left.right == null){ sum += root.left.val; } } sumOfLeftLeaves(root.left); sumOfLeftLeaves(root.right); return sum; }
十四、LC543 二叉树的最大直径【最大路径长度】
class Solution { private int max = 0; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return max; } private int dfs(TreeNode root) { if (root == null) { return 0; } int leftHeight = dfs(root.left); int rightHeight = dfs(root.right); max = Math.max(leftHeight + rightHeight, max); return Math.max(leftHeight, rightHeight) + 1; } }
十五、LC102 二叉树层次优先遍历
// 深度优先遍历： void dfs(TreeNode root) { if (root == null) { return; } dfs(root.left); dfs(root.right); } // 广度优先遍历 void bfs(TreeNode root) { Queue<TreeNode> queue = new ArrayDeque<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); // Java 的 pop 写作 poll() if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } }
这个题目层次遍历，应该选用BFS
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ret = new ArrayList<List<Integer>>(); if (root == null) { return ret; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { List<Integer> level = new ArrayList<Integer>(); int currentLevelSize = queue.size(); for (int i = 1; i <= currentLevelSize; ++i) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } ret.add(level); } return ret; } }
