JZ55 二叉树的深度
1 /* 递归 */ 2 public class JZ55_1 3 { 4 public static int TreeDepth(TreeNode root) 5 { 6 if (root == null) return 0; 7 return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1; 8 } 9 } 10 11 /* 层次遍历 */ 12 public class JZ55_2 13 { 14 public static int TreeDepth(TreeNode root) 15 { 16 if (root == null) return 0; 17 Queue<TreeNode> queue = new LinkedList<>(); 18 int size = -1, res = 0; 19 queue.add(root); 20 while (!queue.isEmpty()) 21 { 22 size = queue.size(); 23 while (size != 0) 24 { 25 TreeNode poll = queue.poll(); 26 if (poll.left != null) 27 queue.add(poll.left); 28 if (poll.right != null) 29 queue.add(poll.right); 30 size--; 31 } 32 res++; 33 } 34 return res; 35 } 36 }
JZ77 按之字形顺序打印二叉树
1 /* 模拟 */ 2 public class JZ77_1 3 { 4 public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) 5 { 6 ArrayList<ArrayList<Integer>> res = new ArrayList<>(); 7 if (pRoot == null) return res; 8 Queue<TreeNode> queue = new LinkedList<>(); 9 boolean revFlag = false; 10 queue.add(pRoot); 11 while (!queue.isEmpty()) 12 { 13 ArrayList<Integer> temp = new ArrayList<>(); 14 int size = queue.size(); 15 while (size != 0) 16 { 17 TreeNode poll = queue.poll(); 18 temp.add(poll.val); 19 if (poll.left != null) 20 queue.add(poll.left); 21 if (poll.right != null) 22 queue.add(poll.right); 23 size--; 24 } 25 if (revFlag) 26 Collections.reverse(temp); 27 res.add(temp); 28 revFlag = !revFlag; 29 } 30 return res; 31 } 32 } 33 34 /* 双栈法 */ 35 public class JZ77_2 36 { 37 public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) 38 { 39 ArrayList<ArrayList<Integer>> res = new ArrayList<>(); 40 Stack<TreeNode> stack1 = new Stack<>(); 41 Stack<TreeNode> stack2 = new Stack<>(); 42 if (pRoot != null) 43 stack1.push(pRoot); 44 while (!stack1.isEmpty() || !stack2.isEmpty()) 45 { 46 ArrayList<Integer> temp = new ArrayList<>(); 47 if (!stack1.isEmpty()) 48 { 49 while (!stack1.isEmpty()) 50 { 51 TreeNode popNode = stack1.pop(); 52 temp.add(popNode.val); 53 if (popNode.left != null) 54 stack2.push(popNode.left); 55 if (popNode.right != null) 56 stack2.push(popNode.right); 57 } 58 } 59 else 60 { 61 while (!stack2.isEmpty()) 62 { 63 TreeNode popNode = stack2.pop(); 64 temp.add(popNode.val); 65 if (popNode.right != null) 66 stack1.push(popNode.right); 67 if (popNode.left != null) 68 stack1.push(popNode.left); 69 } 70 } 71 res.add(temp); 72 } 73 return res; 74 } 75 }
JZ54 二叉搜索树的第k个节点
1 /* 递归 */ 2 public class JZ54_1 3 { 4 public static int num; 5 6 public static int KthNode(TreeNode proot, int k) 7 { 8 num = k; 9 return inorder(proot); 10 } 11 12 private static int inorder(TreeNode proot) 13 { 14 if (proot != null) 15 { 16 int left = inorder(proot.left); 17 if (left != -1) 18 return left; 19 if (num == 1) 20 return proot.val; 21 num--; 22 return inorder(proot.right); 23 } 24 return -1; 25 } 26 } 27 28 /* 非递归 */ 29 public class JZ54_2 30 { 31 public static int KthNode(TreeNode proot, int k) 32 { 33 Stack<TreeNode> stack = new Stack<>(); 34 while (!stack.isEmpty() || proot != null) 35 { 36 if (proot != null) 37 { 38 stack.push(proot); 39 proot = proot.left; 40 } 41 else 42 { 43 TreeNode popNode = stack.pop(); 44 if (k == 1) return popNode.val; 45 k--; 46 proot = popNode.right; 47 } 48 } 49 return -1; 50 } 51 }
JZ7 重建二叉树
1 /* 递归 */ 2 public class JZ7_1 3 { 4 public static TreeNode reConstructBinaryTree(int[] preOrder, int[] vinOrder) 5 { 6 return struct(preOrder, 0, preOrder.length - 1, vinOrder, 0, vinOrder.length - 1); 7 } 8 9 public static TreeNode struct(int[] preOrder, int preS, int preE, int[] vinOrder, int vinS, int vinE) 10 { 11 if (preS > preE || vinS > vinE) return null; 12 TreeNode root = new TreeNode(preOrder[preS]); 13 int pivot = vinS; 14 while (vinOrder[pivot] != preOrder[preS]) 15 pivot++; 16 int len = pivot - vinS; 17 root.left = struct(preOrder, preS + 1, preS + len, vinOrder, vinS, pivot - 1); 18 root.right = struct(preOrder, preS + len + 1, preE, vinOrder, pivot + 1, vinE); 19 return root; 20 } 21 }
JZ26 树的子结构⭐
1 /* 递归 */ 2 public class JZ26_1 3 { 4 public static boolean HasSubtree(TreeNode root1, TreeNode root2) 5 { 6 if (root2 == null) return false; 7 else return fun(root1, root2); 8 } 9 10 public static boolean fun(TreeNode root1, TreeNode root2) 11 { 12 if (root2 == null) return true; 13 if (root1 == null) return false; 14 boolean one = (root1.val == root2.val) && fun(root1.left, root2.left) && fun(root1.right, root2.right); 15 if (one) return true; 16 boolean two = fun(root1.left, root2) || fun(root1.right, root2); 17 return two; 18 } 19 } 20 21 /* 递归版本2 */ 22 public class JZ26_2 23 { 24 public static boolean HasSubtree(TreeNode root1, TreeNode root2) 25 { 26 boolean res = false; 27 if (root1 != null && root2 != null) 28 { 29 if (root1.val == root2.val) 30 res = judge(root1, root2); 31 if (!res) 32 res = HasSubtree(root1.left, root2); 33 if (!res) 34 res = HasSubtree(root1.right, root2); 35 } 36 return res; 37 } 38 39 public static boolean judge(TreeNode root1, TreeNode root2) 40 { 41 if (root2 == null) return true; 42 if (root1 == null) return false; 43 if (root1.val != root2.val) return false; 44 return judge(root1.left, root2.left) && judge(root1.right, root2.right); 45 } 46 }
JZ27 二叉树的镜像
1 /* 递归 */ 2 public class JZ7_1 3 { 4 public static TreeNode reConstructBinaryTree(int[] preOrder, int[] vinOrder) 5 { 6 return struct(preOrder, 0, preOrder.length - 1, vinOrder, 0, vinOrder.length - 1); 7 } 8 9 public static TreeNode struct(int[] preOrder, int preS, int preE, int[] vinOrder, int vinS, int vinE) 10 { 11 if (preS > preE || vinS > vinE) return null; 12 TreeNode root = new TreeNode(preOrder[preS]); 13 int pivot = vinS; 14 while (vinOrder[pivot] != preOrder[preS]) 15 pivot++; 16 int len = pivot - vinS; 17 root.left = struct(preOrder, preS + 1, preS + len, vinOrder, vinS, pivot - 1); 18 root.right = struct(preOrder, preS + len + 1, preE, vinOrder, pivot + 1, vinE); 19 return root; 20 } 21 }
JZ32 从上往下打印二叉树
1 /* 层次遍历 */ 2 public class JZ32_1 3 { 4 public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root) 5 { 6 ArrayList<Integer> res = new ArrayList<>(); 7 Queue<TreeNode> queue = new LinkedList<>(); 8 if (root == null) return res; 9 queue.add(root); 10 while (!queue.isEmpty()) 11 { 12 TreeNode poll = queue.poll(); 13 res.add(poll.val); 14 if (poll.left != null) 15 queue.add(poll.left); 16 if (poll.right != null) 17 queue.add(poll.right); 18 } 19 return res; 20 } 21 } 22 23 /* 递归 */ 24 public class JZ32_2 25 { 26 public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root) 27 { 28 ArrayList<ArrayList<Integer>> temp = new ArrayList<>(); 29 ArrayList<Integer> res = new ArrayList<>(); 30 levelTravel(root, temp, 1); 31 for (ArrayList<Integer> list : temp) 32 res.addAll(list); 33 return res; 34 } 35 36 public static void levelTravel(TreeNode root, ArrayList<ArrayList<Integer>> temp, int depth) 37 { 38 if (root == null) return; 39 if (temp.size() < depth) 40 { 41 ArrayList<Integer> addList = new ArrayList<>(); 42 addList.add(root.val); 43 temp.add(addList); 44 } 45 else 46 { 47 temp.get(depth - 1).add(root.val); 48 } 49 levelTravel(root.left, temp, depth + 1); 50 levelTravel(root.right, temp, depth + 1); 51 } 52 }
JZ33 二叉搜索树的后序遍历序列
1 /* 递归 */ 2 public class JZ33_1 3 { 4 public static boolean VerifySquenceOfBST(int[] sequence) 5 { 6 if (sequence.length == 0) return false; 7 return judge(sequence, 0, sequence.length - 1); 8 } 9 10 public static boolean judge(int[] sequence, int left, int right) 11 { 12 if (left >= right) return true; 13 int idx = left; 14 while (sequence[idx] < sequence[right] && idx < right) 15 idx++; 16 for (int i = idx; i < right; i++) 17 { 18 if (sequence[i] < sequence[right]) 19 return false; 20 } 21 return judge(sequence, left, idx - 1) && judge(sequence, idx, right - 1); 22 } 23 } 24 25 /* ⭐若将中序序列当作入栈序列,那么后序序列应该是合法的出栈序列⭐ */ 26 public class JZ33_2 27 { 28 public static boolean VerifySquenceOfBST(int[] sequence) 29 { 30 if (sequence.length == 0) return false; 31 int j = 0; 32 ArrayList<Integer> inOrder = new ArrayList<>(); 33 Stack<Integer> stack = new Stack<>(); 34 for (int num : sequence) inOrder.add(num); 35 Collections.sort(inOrder); 36 for (int num : inOrder) 37 { 38 stack.add(num); 39 while (!stack.isEmpty() && stack.peek() == sequence[j]) 40 { 41 stack.pop(); 42 j++; 43 } 44 } 45 return j == sequence.length; 46 } 47 }
JZ82 二叉树中和为某一值的路径(一)
1 /* 递归 */ 2 public class JZ82_1 3 { 4 public static boolean hasPathSum(TreeNode root, int sum) 5 { 6 if (root == null) 7 return false; 8 if (root.left == null && root.right == null && sum - root.val == 0) 9 return true; 10 return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); 11 } 12 } 13 14 /* 层次 */ 15 public class JZ82_2 16 { 17 public static boolean hasPathSum(TreeNode root, int sum) 18 { 19 if (root == null) return false; 20 Queue<TreeNode> queue = new LinkedList<>(); 21 queue.add(root); 22 while (!queue.isEmpty()) 23 { 24 TreeNode pollNode = queue.poll(); 25 if (pollNode.left != null) 26 { 27 pollNode.left.val += pollNode.val; 28 queue.add(pollNode.left); 29 30 } 31 if (pollNode.right != null) 32 { 33 pollNode.right.val += pollNode.val; 34 queue.add(pollNode.right); 35 } 36 if (pollNode.val == sum && pollNode.left == null && pollNode.right == null) 37 return true; 38 } 39 return false; 40 } 41 }
JZ34 二叉树中和为某一值的路径(二)
1 /* DFS */ 2 public class JZ34_1 3 { 4 public static ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 5 6 public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) 7 { 8 if (root == null) return res; 9 dfs(root, target, new ArrayList<Integer>()); 10 return res; 11 } 12 13 public static void dfs(TreeNode root, int target, ArrayList<Integer> path) 14 { 15 path.add(root.val); 16 target -= root.val; 17 if (root.left == null && root.right == null && target == 0) 18 res.add(new ArrayList<>(path)); 19 if (root.left != null) 20 dfs(root.left, target, path); 21 if (root.right != null) 22 dfs(root.right, target, path); 23 path.remove(path.size() - 1); 24 } 25 }标签:right,return,offer,int,null,root,public From: https://www.cnblogs.com/VividBinGo/p/17721156.html