《春节7天练Day5：二叉树和堆.pdf》由会员分享，可在线阅读，更多相关《春节7天练Day5：二叉树和堆.pdf（13页珍藏版）》请在三一文库上搜索。
1、春节7天练|Day5：二叉树和堆 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/春节7天练Day5：二叉树和堆.html2019/2/10 21:38:02 春节7天练|Day5：二叉树和堆 你好，我是王争。春节假期进入尾声了。你现在是否已经准备返回工作岗位了呢？今天更新的是测试题的第五篇，我们继续来复习。 关于二叉树和堆的7个必知必会的代码实现 二叉树 实现一个二叉查找树，并且支持插入、删除、查找操作 实现查找二叉查找树中某个节点的后继、前驱节点 实现二叉树前、中、后序以及按层遍历 堆 实现一个小顶堆、大顶堆、优先级队列 实现堆排序 利用
2、优先级队列合并K个有序数组 求一组动态数据集合的最大Top K 对应的LeetCode练习题（Smallfly 整理） Invert Binary Tree（翻转二叉树） 英文版：https:/ 中文版：https:/leetcode- Maximum Depth of Binary Tree（二叉树的最大深度） 英文版：https:/ 中文版：https:/leetcode- Validate Binary Search Tree（验证二叉查找树） 春节7天练|Day5：二叉树和堆 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/春节7天练
3、Day5：二叉树和堆.html2019/2/10 21:38:02 英文版：https:/ 中文版：https:/leetcode- Path Sum（路径总和） 英文版：https:/ 中文版：https:/leetcode- 做完题目之后，你可以点击“请朋友读”，把测试题分享给你的朋友。 祝你取得好成绩！明天见！ 春节7天练|Day5：二叉树和堆 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/春节7天练Day5：二叉树和堆.html2019/2/10 21:38:02 精选留言： 李皮皮皮皮皮 2019-02-09 09:00:59 平
4、衡树的各种操作太烧脑了，左旋右旋，红黑树就更别提了。过段时间就忘。 2赞 春节7天练|Day5：二叉树和堆 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/春节7天练Day5：二叉树和堆.html2019/2/10 21:38:02 纯洁的憎恶 2019-02-10 00:32:06 今天的题目很适合递归实现，当然递归公式离代码实现还是存在一定距离。 1.翻转二叉树（T） 当T为Null时则返回； 翻转二叉树（T的左子树）； 翻转二叉树（T的右子树）； 若T不为叶节点，则交换T的左右子树位置； 2.最大深度（T） 当T为Null时，retur
5、n 0； return Max（最大深度（T左子树）+1，最大深度（T右子树）+1）； 函数返回值即为最大深度。 3.验证二叉查找树（T， int rightDepth = maxDepth(root - right); return 1 + (leftDepth rightDepth ? leftDepth : rightDepth); ; _CountingStars 2019-02-09 13:10:01 二叉树的最大深度 go 语言实现 /* * Definition for a binary tree node. 春节7天练|Day5：二叉树和堆 file:/J/geektime/唯
6、一更新QQ群170701297/ebook/数据结构与算法之美/春节7天练Day5：二叉树和堆.html2019/2/10 21:38:02 * 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 != n
7、il rightDepth = maxDepth(root.Right) if leftDepth = rightDepth return leftDepth + 1 else return rightDepth + 1 _CountingStars 2019-02-09 12:55:24 翻转二叉树 go 语言实现 /* * Definition for a binary tree node. 春节7天练|Day5：二叉树和堆 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/春节7天练Day5：二叉树和堆.html2019/2/10 21:
8、38:02 * type TreeNode struct * Val int * Left *TreeNode * Right *TreeNode * */ func invertTree(root *TreeNode) *TreeNode if root = nil return nil if root.Left != nil root.Left = invertTree(root.Left) if root.Right != nil root.Right = invertTree(root.Right) root.Left, root.Right = root.Right, root.Le
9、ft return root C_love 2019-02-09 09:41:32 Path Sum /* * Definition for a binary tree node. * public class TreeNode * int val; * TreeNode left; 春节7天练|Day5：二叉树和堆 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/春节7天练Day5：二叉树和堆.html2019/2/10 21:38:02 * TreeNode right; * TreeNode(int x) val = x; * * Ti
10、me and space complexity: O(n) */ class Solution public boolean hasPathSum(TreeNode root, int sum) if (root = null) return false; if (root.left = null return hasPathSum(root.left, sum - root.val) | hasPathSum(root.right, sum - root.val); 失火的夏天 2019-02-09 00:11:25 / 翻转二叉树 public TreeNode invertTree(Tr
11、eeNode root) if(root = null) return root; TreeNode node = root; Queue queue = new LinkedList(); TreeNode node = root; TreeNode preNode = null; while(node != null | !stack.isEmpty() stack.push(node); node = node.left; while(node = null if(preNode != null) if(preNode.val = node.val) return false; preN
12、ode = node; 春节7天练|Day5：二叉树和堆 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/春节7天练Day5：二叉树和堆.html2019/2/10 21:38:02 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 hasPath
13、Sum(TreeNode root, int tmp, int sum) if (root = null) return false; if (root.left = null 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);