精选留言(33)

• 
  李皮皮皮皮皮

  2019-02-09

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

  

  20
• 
  kai

  2019-02-11

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

  展开

  

  5
• 
  失火的夏天

  2019-02-09

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

  

  4
• 
  星夜

  2020-11-27

  二叉查找树节点删除逻辑，不知道对不对： 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; }

  展开

  

  1
• 
  Abner

  2019-02-14

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

  展开

  

  1
• 
  kai

  2019-02-11

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

  展开

  

  2
• 
  kai

  2019-02-10

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

  

  1
• 
  纯洁的憎恶

  2019-02-10

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

  展开

  

  1
• 
  mgxian

  2019-02-09

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

  展开

  

  1
• 
  云之崖

  2021-01-07

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

  

  
• 
  jianhuang_zou

  2020-04-05

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

  

  
• 
  jianhuang_zou

  2020-04-05

  二叉树的两种解法，一下解释为中序遍历，将代码调整顺序，可得到前序和后序遍历结果（转） # # 递归法 # 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

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

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

  

  
• 
  懒猫

  2019-06-14

  打卡

  

  
• 
  DigDeeply

  2019-04-01

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

  

  
• 
  hopeful

  2019-03-11

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

  展开

  

  
• 
  hopeful

  2019-03-05

  #实现小顶堆 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

  展开

  

  
• 
  hopeful

  2019-03-05

  #实现大顶堆 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

  展开

  

  
• 
  hopeful

  2019-03-05

  #堆排序 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)

  展开

  

  
• 
  Sharry

  2019-02-25

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

  展开

  

  