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

精选留言(29)

• 

  李皮皮皮皮皮

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

  2019-02-09

  

   8
• 

  kai

  树的前中后序遍历-递归实现：
  
  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-11

  

   2
• 

  kai

  树的前中后序遍历-非递归实现：
  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();
      }
  }
  

  2019-02-11

  

   1
• 

  kai

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

  2019-02-10

  

   1
• 

  纯洁的憎恶

  今天的题目很适合递归实现，当然递归公式离代码实现还是存在一定距离。
  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时则存在于目标值相同的路径之和；

  2019-02-10

  

   1
• 

  _CountingStars

  二叉树的最大深度 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
      }
  }

  2019-02-09

  

   1
• 

  失火的夏天

  // 翻转二叉树
  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-09

  

   1
• 

  啵啵啵

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

  作者回复: 要不要保时捷也送你一辆啊

  2019-10-06

  

  
• 

  懒猫

  打卡

  2019-06-14

  

  
• 

  付坤

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

  2019-04-01

  

  
• 

  hopeful

  #验证二叉搜索树
  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
  

  2019-03-11

  

  
• 

  hopeful

  #实现小顶堆
  def makeSmallHeap(array):
      for i in range(int(len(array)/2) , -1 , -1):
          makeHeap(array , i , len(array))
  def makeHeap(array , i ,N):
      while 2*i+1 < N:
          child = 2*i+1
          if child != N-1 and array[child] > array[child+1]:
              child+=1
          if array[child] < array[i]:
              temp = array[child]
              array[child] = array[i]
              array[i] = temp
              i = child
          else:
              break

  2019-03-05

  

  
• 

  hopeful

  #实现大顶堆
  def makeBigHeap(array):
      for i in range(int(len(array)/2) , -1 , -1):
          makeHeap(array , i , len(array))
  def makeHeap(array , i ,N):
      while 2*i+1 < N:
          child = 2*i+1
          if child != N-1 and array[child] < array[child+1]:
              child+=1
          if array[child] > array[i]:
              temp = array[child]
              array[child] = array[i]
              array[i] = temp
              i = child
          else:
              break

  2019-03-05

  

  
• 

  hopeful

  #堆排序
  import random
  import time
  
  def Array(n):
      a = []
      for i in range(n):
          a.append(random.randint(0 , n))
      return a
  
  def makeHeap(array , i ,N):
      while 2*i+1 < N:
          child = 2*i+1
          if child != N-1 and array[child] < array[child+1]:
              child+=1
          if array[child] > array[i]:
              temp = array[child]
              array[child] = array[i]
              array[i] = temp
              i = child
          else:
              break
  def heapSort():
      array = Array(100)
      for i in range(int(len(array)/2) , -1 , -1):
          makeHeap(array , i , len(array))
      for i in range(len(array)-1 , -1 , -1):
          temp = array[0]
          array[0] = array[i]
          array[i] = temp
          makeHeap(array , 0 , i)
      print(array)

  2019-03-05

  

  
• 

  Sharry

  路径总和: 使用回溯法, 遍历每一条 root->leaf 的路线是否满足在和为 sum, 可以使用减枝操作
  
  二叉树深度 = 左右子树中深度最大者 + 1
  
  验证二叉搜索树:
  1. 遍历每一个结点, 若都满足, 当前结点大于左子树中的最大值, 小于右子树中的最小值, 则说明为二叉搜索树
  2. 中序遍历二叉搜索树, 若序列递增, 则说明为二叉搜索树

  2019-02-25

  

  
• 

  hopeful

  #二叉树前中后序及层次遍历非递归版本
  class Tree:
      def __init__(self, x):
          self.val = x
          self.left = None
          self.right = None
  
  #----前序----
  def preOrder(Tree T):
      if T is None:
          return []
      list1 = []
      list2 = []
      list1.append(T)
      while len(list1) > 0:
          t = list1.pop()
          list2.append(t)
          if t.right not None:
              list1.append(t.right)
          if t.left not None:
              list1.append(t.left)
      return list2
  
  #----中序----
  def inOrder(Tree T):
      if T is None:
          return []
      list1 = []
      list2 = []
      while T or len(list1)>0 :
          if T :
              list1.append(T)
              T = T.left
          else:
              T = list1.pop()
              list2.append(T)
              T = T.right
      return list2
  
  #----后序----
  def postOrder(Tree T):
      if T is None:
          return []
      list1 = []
      list2 = []
      list1.append(T)
      while len(list1)>0 :
          t = list1.pop()
          list2.append(t)
          if t.left not None:
              list1.append(t.left)
          if t.right not None:
              list1.append(t.right)
      return list2[::-1]
  
  #----层次-----
  def levelOrder():
      if T is None:
          return []
      list1 = []
      list2 = []
      list1.append(T)
      while len(list1)>0 :
          t = list1[0]
          del list1[0]
          list2.append(t)
          if t.left not None:
              list1.append(t.left)
          if t.right not None:
              list1.append(t.right)
      return list2
  

  2019-02-16

  

  
• 

  abner

  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);
              }
          }
      }
  }
  

  2019-02-14

  

  
• 

  拉欧

  Path Sum（路径总和）go 语言实现
  func hasPathSum(root *TreeNode, sum int) bool {
  
  if root==nil{
  return false
  }
  if root.Left==nil && root.Right==nil{
  if root.Val==sum{
  return true
  }else{
  return false
  }
  
  }
  left:=false
  if root.Left!=nil{
  left=hasPathSum(root.Left,sum-root.Val)
  }
  right:=false
  if root.Right!=nil{
  right=hasPathSum(root.Right,sum-root.Val)
  }
  return left || right
  }

  2019-02-14

  

  
• 

  拉欧

  Validate Binary Search Tree（验证二叉查找数） go语言实现
  
  func isValidBST(root *TreeNode) bool {
  
  if root==nil{
  return true
  }
  less:=true
  more:=true
  if root.Left!=nil{
  less=JudgeLess(root.Left,root.Val)
  }
  if root.Right!=nil{
  more=JudgeMore(root.Right,root.Val)
  }
  if ! (less && more){
  return false
  }else{
  return isValidBST(root.Left) && isValidBST(root.Right)
  }
  }
  
  func JudgeLess(root *TreeNode,num int) bool{
  
  if root.Val>=num{
  return false
  }
  if root.Left!=nil && root.Right!=nil{
  return JudgeLess(root.Left,num) && JudgeLess(root.Right,num)
  }else if root.Left!=nil{
  return JudgeLess(root.Left,num)
  }else if root.Right!=nil{
  return JudgeLess(root.Right,num)
  }else{
  return true
  }
  }
  
  func JudgeMore(root *TreeNode,num int) bool{
  if root.Val<=num{
  return false
  }
  if root.Left!=nil && root.Right!=nil{
  return JudgeMore(root.Left,num) && JudgeMore(root.Right,num)
  }else if root.Left!=nil{
  return JudgeMore(root.Left,num)
  }else if root.Right!=nil{
  return JudgeMore(root.Right,num)
  }else{
  return true
  }
  }
  

  2019-02-14

  

  
• 

  拉欧

  Invert Binary Tree（翻转二叉树） go 语言实现
  func invertTree(root *TreeNode) *TreeNode {
  if root==nil{
  return root
  }
  temp:=root.Left
  root.Left=root.Right
  root.Right=temp
  invertTree(root.Left)
  invertTree(root.Right)
  return root
  }

  2019-02-14

  

  