春节7天练 | Day 5：二叉树和堆

精选留言

• 
  李皮皮皮皮皮

  2019-02-09 09:00:59

  平衡树的各种操作太烧脑了，左旋右旋，红黑树就更别提了。过段时间就忘。😢
• kai

  2019-02-11 11:05:02

  树的前中后序遍历-递归实现：
  
  public class TreeTraversal {
  
  public static class Node {
  public int value;
  public Node left;
  public Node right;
  
  public Node(int value) {
  this.value = value;
  }
  }
  
  // 二叉树的递归遍历
  public static void preOrderRecursive(Node head) {
  if (head == null) {
  return;
  }
  
  System.out.print(head.value + " ");
  preOrderRecursive(head.left);
  preOrderRecursive(head.right);
  }
  
  public static void inOrderRecursive(Node head) {
  if (head == null) {
  return;
  }
  
  inOrderRecursive(head.left);
  System.out.print(head.value + " ");
  inOrderRecursive(head.right);
  }
  
  public static void postOrderRecursive(Node head) {
  if (head == null) {
  return;
  }
  
  postOrderRecursive(head.left);
  postOrderRecursive(head.right);
  System.out.print(head.value + " ");
  }
  
  }
  
• 
  失火的夏天

  2019-02-09 00:11:25

  // 翻转二叉树
  public TreeNode invertTree(TreeNode root) {
  if(root == null){
  return root;
  }
  TreeNode node = root;
  Queue<TreeNode> queue = new LinkedList<>();
  queue.add(node);
  while(!queue.isEmpty()){
  node = queue.poll();
  TreeNode tempNode = node.left;
  node.left = node.right;
  node.right = tempNode;
  if(node.left != null){
  queue.offer(node.left);
  }
  if(node.right != null){
  queue.offer(node.right);
  }
  }
  return root;
  }
  // 二叉树的最大深度
  public int maxDepth(TreeNode root) {
  if(root == null) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
  }
  // 验证二叉查找树
  public boolean isValidBST(TreeNode root) {
  if (root == null) {
  return true;
  }
  Stack<TreeNode> stack = new Stack<>();
  TreeNode node = root;
  TreeNode preNode = null;
  while(node != null || !stack.isEmpty()){
  stack.push(node);
  node = node.left;
  while(node == null && !stack.isEmpty()){
  node = stack.pop();
  if(preNode != null){
  if(preNode.val >= node.val){
  return false;
  }
  }
  preNode = node;
  node = node.right;
  }
  }
  return true;
  }
  // 路径总和
  public boolean hasPathSum(TreeNode root, int sum) {
  if (root == null) {
  return false;
  }
  return hasPathSum(root, root.val, sum);
  }
  
  public boolean hasPathSum(TreeNode root, int tmp, int sum) {
  if (root == null) {
  return false;
  }
  if (root.left == null && root.right == null) {
  return tmp == sum;
  }
  if (root.left == null) {
  return hasPathSum(root.right, root.right.val + tmp, sum);
  }
  if (root.right == null) {
  return hasPathSum(root.left, root.left.val + tmp, sum);
  }
  return hasPathSum(root.left, root.left.val + tmp, sum) ||
  hasPathSum(root.right, root.right.val + tmp, sum);
  }

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 10:55:53

• kai

  2019-02-11 11:06:35

  树的前中后序遍历-非递归实现：
  import java.util.Stack;
  
  
  public class TreeTraversal {
  public static class Node {
  public int value;
  public Node left;
  public Node right;
  public Node(int value) {
  this.value = value;
  }
  }
  // 二叉树的非递归遍历
  public static void preOrder(Node head) {
  System.out.print("pre-order: ");
  if (head == null) {
  return;
  }
  Stack<Node> s = new Stack<>();
  s.push(head);
  while (!s.isEmpty()) {
  head = s.pop();
  System.out.print(head.value + " ");
  if (head.right != null) {
  s.push(head.right);
  }
  
  if (head.left != null) {
  s.push(head.left);
  }
  }
  System.out.println();
  }
  
  public static void inOrder(Node head) {
  System.out.print("in-order: ");
  if (head == null) {
  return;
  }
  Stack<Node> s = new Stack<>();
  while (!s.isEmpty() || head != null) {
  if (head != null) {
  s.push(head);
  head = head.left;
  } else {
  head = s.pop();
  System.out.print(head.value + " ");
  head = head.right;
  }
  }
  System.out.println();
  }
  
  public static void postOrder(Node head) {
  System.out.print("pos-order: ");
  if (head == null) {
  return;
  }
  
  Stack<Node> tmp = new Stack<>();
  Stack<Node> s = new Stack<>();
  
  tmp.push(head);
  while(!tmp.isEmpty()) {
  head = tmp.pop();
  s.push(head);
  
  if (head.left != null) {
  tmp.push(head.left);
  }
  
  if (head.right != null) {
  tmp.push(head.right);
  }
  }
  
  while (!s.isEmpty()) {
  System.out.print(s.pop().value + " ");
  }
  
  System.out.println();
  }
  }
  
• 
  星夜

  2020-11-27 20:33:25

  二叉查找树节点删除逻辑，不知道对不对：
  public boolean removeNode(int val) {
  if (null == root) {
  return false;
  }
  
  if (root.val == val) {
  // 根节点
  root = replace(root);
  } else {
  Node parent = findParent(val);
  if (null == parent) {
  return false;
  }
  if (parent.left.val == val) {
  parent.left = replace(parent.left);
  } else if (parent.right.val == val) {
  parent.right = replace(parent.right);
  }
  }
  return true;
  }
  
  private Node replace(Node cur) {
  Node res = null;
  if (cur.left != null && cur.right != null) {
  res = cur.left;
  res.left = replace(cur.left);
  res.right = cur.right;
  } else if (cur.left != null) {
  res = cur.left;
  } else if (cur.right != null) {
  return cur.right;
  }
  // 置空
  cur.left = null;
  cur.right = null;
  return res;
  }
• 
  Abner

  2019-02-14 23:13:12

  java实现二叉树前序、中序、后序和层次遍历
  代码如下：
  package tree;
  
  import java.util.LinkedList;
  import java.util.Queue;
  
  public class BinaryTree {
  
  private Node root = null;
  
  public static class Node {
  
  private String data;
  private Node left;
  private Node right;
  
  public Node(String data, Node left, Node right) {
  this.data = data;
  this.left = left;
  this.right = right;
  }
  }
  
  public void preOrder(Node root) {
  if (null == root) {
  return ;
  }
  System.out.print(root.data + " ");
  preOrder(root.left);
  preOrder(root.right);
  }
  
  public void inOrder(Node root) {
  if (null == root) {
  return ;
  }
  inOrder(root.left);
  System.out.print(root.data + " ");
  inOrder(root.right);
  }
  
  public void postOrder(Node root) {
  if (null == root) {
  return ;
  }
  postOrder(root.left);
  postOrder(root.right);
  System.out.print(root.data + " ");
  }
  
  public void traverseByLayer(Node root) {
  if (null == root) {
  return ;
  }
  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  while (!queue.isEmpty()) {
  Node pNode = queue.peek();
  System.out.print(pNode.data + " ");
  queue.poll();
  if (root.left != null) {
  queue.add(root.left);
  }
  if (root.right != null) {
  queue.add(root.right);
  }
  }
  }
  }
  
• kai

  2019-02-10 02:29:24

  今天看了一下这一节的题目，发现校招面试的时候都考过，今天又刷了一下，总结了一波，相应的知识点也总结了一下~
• 
  纯洁的憎恶

  2019-02-10 00:32:06

  今天的题目很适合递归实现，当然递归公式离代码实现还是存在一定距离。
  1.翻转二叉树（T）｛
  当T为Null时则返回；
  翻转二叉树（T的左子树）；
  翻转二叉树（T的右子树）；
  若T不为叶节点，则交换T的左右子树位置；
  ｝
  
  2.最大深度（T）｛
  当T为Null时，return 0；
  return Max（最大深度（T左子树）+1，最大深度（T右子树）+1）；
  ｝
  函数返回值即为最大深度。
  
  3.验证二叉查找树（T，&最大值，&最小值）｛
  当T为Null时，return true；
  当T为叶节点时，最小值=最大值=当前节点，返回true；
  左最大值=左最小值=T的值；
  验证二叉查找树（T的左子树，&左最大值，&左最小值）；
  右最大值=右最小值=T的值；
  验证（T的右子树，&右最大值，&右最小值）；
  T的值小于等于右最小值，并且大于等于左最大值时，最大值=右最大值，最小值=左最小值，之后返回true，否则返回false并结束。
  ｝
  函数最终返回true则验证成功。
  
  4.计算路径和（T，sum）｛
  若T为Null返回false；
  若T是叶节点，如果sum+T的值=目标值则返回true并结束，否则返回false；
  计算路径和（T的左子树，sum+T的值）；
  计算路径和（T的右子树，sum+T的值）；
  ｝
  计算路径和（T，0）返回true时则存在于目标值相同的路径之和；
• 
  mgxian

  2019-02-09 13:10:01

  二叉树的最大深度 go 语言实现
  /**
  * Definition for a binary tree node.
  * type TreeNode struct {
  * Val int
  * Left *TreeNode
  * Right *TreeNode
  * }
  */
  func maxDepth(root *TreeNode) int {
  if root == nil {
  return 0
  }
  
  leftDepth :=0
  rightDepth :=0
  if root.Left != nil {
  leftDepth = maxDepth(root.Left)
  }
  
  if root.Right != nil {
  rightDepth = maxDepth(root.Right)
  }
  
  if leftDepth >= rightDepth {
  return leftDepth + 1
  } else {
  return rightDepth + 1
  }
  }
• 
  杨建斌(young)

  2023-07-03 11:35:05

  路径总和
  private static boolean deep(TreeNode treeNode, int targetSum, int curr) {
  if (treeNode == null && curr == targetSum) {
  return true;
  }
  if (treeNode == null) {
  return false;
  }
  if (curr >= targetSum) {
  return false;
  }
  return deep(treeNode.left, targetSum, curr + treeNode.val) || deep(treeNode.right, targetSum, curr + treeNode.val);
  }
• 
  杨建斌(young)

  2023-07-03 11:19:05

  验证二叉查找树
  private static boolean deep(TreeNode treeNode) {
  if (treeNode == null) {
  return true;
  }
  int val = treeNode.val;
  if (treeNode.left != null && treeNode.left.val > val) {
  return false;
  }
  if (treeNode.right != null && treeNode.right.val < val) {
  return false;
  }
  return deep(treeNode.left) && deep(treeNode.right);
  }
• 
  杨建斌(young)

  2023-07-03 10:50:52

  最大深度
  private static int deep(TreeNode treeNode, int dep) {
  if (treeNode == null) {
  return dep;
  }
  return Math.max(deep(treeNode.left, dep + 1), deep(treeNode.right, dep + 1));
  }
• 
  杨建斌(young)

  2023-07-03 10:37:39

  翻转二叉树
  public static void main(String[] args) {
  TreeNode treeNode = new TreeNode(4);
  treeNode.left = new TreeNode(2);
  treeNode.left.left = new TreeNode(1);
  treeNode.left.right = new TreeNode(3);
  
  treeNode.right = new TreeNode(7);
  treeNode.right.left = new TreeNode(6);
  treeNode.right.right = new TreeNode(9);
  
  xx(treeNode);
  
  System.out.println(treeNode);
  
  }
  
  private static void xx(TreeNode treeNode) {
  if (treeNode == null) {
  return;
  }
  TreeNode left = treeNode.left;
  treeNode.left = treeNode.right;
  treeNode.right = left;
  xx(treeNode.left);
  xx(treeNode.right);
  }
• 
  云之崖

  2021-01-07 11:47:37

  现在复习，基本上10分钟之类，能手写搞定堆排序，基本一次就过。还有二叉树的删除操作，现在想明白了原理，间隔再久的时间，纸上画一画，写起来也不会有什么困难。
• 
  jianhuang_zou

  2020-04-05 10:43:34

  迭代是逐渐逼近，用新值覆盖旧值，直到满足条件后结束，不保存中间值，空间利用率高。
  递归是将一个问题分解为若干相对小一点的问题，遇到递归出口再原路返回，因此必须保存相关的中间值，这些中间值压入栈保存，问题规模较大时会占用大量内存。
• 
  jianhuang_zou

  2020-04-05 10:43:12

  二叉树的两种解法，一下解释为中序遍历，将代码调整顺序，可得到前序和后序遍历结果（转）
  # # 递归法
  # if root is None:
  # return[]
  # return self.inorderTraversal(root.left)\
  # +[root.val]\
  # +self.inorderTraversal(root.right)
  # 迭代法
  result=[]
  stack=[(1,root)]
  while stack:
  go_deeper,node=stack.pop()
  if node is None:
  continue
  if go_deeper:
  #左右结点还需深化
  stack.append((1,node.right))
  stack.append((0,node))
  stack.append((1,node.left))
  else:
  result.append(node.val)
  return result
• 
  啵啵啵

  2019-10-06 11:44:25

  作者可以提供pdf版的课程资料吗，不然我觉得不值，因为不能大量复制，不能形成书面笔记，毕竟我付费了。

  作者回复

  要不要保时捷也送你一辆啊

  2019-10-09 08:26:27

• 
  懒猫

  2019-06-14 12:02:56

  打卡
• 
  DigDeeply

  2019-04-01 13:59:02

  https://github.com/DigDeeply/data-structures-learning/blob/0e14f4f69d1f3d45c3d16820cb771f6c242898e4/57-5-binary_tree/binary_tree.go
  
  用数组实现的二叉查找树，支持增删查。
• 
  hopeful

  2019-03-11 10:29:01

  #验证二叉搜索树
  def isValidBST(self, root: TreeNode) -> bool:
  def inorderTraversal(root):
  if root == None:
  return []
  res = []
  res += inorderTraversal(root.left)
  res.append(root.val)
  res += inorderTraversal(root.right)
  return res
  
  res = inorderTraversal(root)
  if res != sorted(list(set(res))): return False
  return True