欢迎来到我的个人网站。交流请加我好友: 919201148。欢迎关注公众号或视频号:蜗牛互联网
Solo  当前访客:4 开始使用

白色蜗牛的互联网心得

我要一步一步往上爬,在最高点乘着叶片往前飞

标签: 树 (6)

剑指Offer之二十五--二叉树中和为某一值的所有路径

2016-04-07 21:10:27 huayonglun
0  评论    214  浏览

题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 解析 先序遍历,将遍历过的结点放到A集合中 当遍历到叶子结点并且和恰好是目标值时,将遍历经过的所有结点放到B集合中,B则是满足题意的一条路径 如果遍历到叶子结点和仍然不等于目标值,那么就移除A集合中添加的结点,修改和,切换到右孩子结点重新计算 如果没有遍历到叶子结点就从孩子结点中继续寻找这样的路径 二叉树定义 class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } 代码实现 public ArrayList<ArrayList<Integer>> findPath(TreeNode root,int target) { /* * currentSum 记录当前和 * pathNodes 保存当前路径扫描过的结点 * ....

, , ,

剑指Offer之二十三--从上往下打印二叉树

2016-04-04 23:43:15 huayonglun
0  评论    214  浏览

二叉树结构 class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } 题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 解析 考察层序遍历 每一次打印一个结点的时候,如果该结点有子节点,则把该结点的子节点放到一个队列的末尾。 接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直至队列中所有的结点都被打印出来为止。 代码实现 public ArrayList<Integer> printFromTopToBottom(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); if(root==null){ return list; } Queue<TreeNode> queue = new LinkedList<TreeNode>....

, , ,

剑指Offer之二十四--二叉搜索树的后序遍历序列

2016-04-05 01:11:13 huayonglun
0  评论    220  浏览

题目描述 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。 如果是则返回ture,否则返回false。 假设输入的数组的任意两个数字都互不相同。 解析 找到根结点 从头遍历序列,第一个比根结点大的元素为右子树的起点 判断右子树是否都比根结点大,若不是返回false,若是,进行下一步 分别把左子树和右子树都以上面规则进行判断,若左右子树都能返回true,则整个序列为二叉搜索树的后序遍历序列,返回true 代码实现 public boolean verifySquenceOfBST(int [] sequence) { if(sequence == null || sequence.length == 0){ return false; } int len = sequence.length; int root = sequence[len - 1]; int i = 0; for(; i < len - 1; i++){ if(sequence[i] > root){ break; } } int j = i; for(;j < len - 1;....

, , ,

剑指Offer之十八--树的子结构

2016-03-27 17:18:30 huayonglun
0  评论    212  浏览

二叉树结构 class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } 题目描述 输入两颗二叉树A,B,判断B是不是A的子结构 解析 二叉树遍历算法的应用 原二叉树是否具有某棵子树,只需要判断每个结点是否都在二叉树中出现即可 第一步在树A中找到和B的根结点的值一样的结点R 第二步再判断树A中以R为根结点的子树是不是包含和树B一样的结构 递归实现 //判断根结点为root1的树是否包含root2结构 public boolean hasSubtree(TreeNode root1,TreeNode root2) { //初始化标记变量为false boolean hasSubtreeFlag = false; //先判断根结点,若不包含判断左孩子,其次是右孩子 if(root1 != null && root2 != null){ if(root1.val == root2.val....

, , ,

剑指Offer之二十七--二叉搜索树与双向链表

2016-04-18 18:48:28 huayonglun
0  评论    216  浏览

二叉树结构 class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路: 由于二叉搜索树的中序遍历就是排序的,如果是构造单链表,只需要一次中序遍历就可以了 但现在需要构造双链表,也就是在中序遍历的过程中需要设置每个结点的left与right指针,现在问题是如何设置这两个指针 二叉搜索树有一个特点,就是根结点的左子树上所有结点都比根结点的值小,而右子树上的所有结点的值都比根结点的值大 利用这个性质,当遍历根结点的左孩子的时候,可以继续把其当做左子树的根结点,右孩子可以当做右子树的根结点,从而使用递归完成 步骤 以左子树为例,依次访问结点的左孩子,当遍历到叶子节点的时候,递归结束,并把该叶子结点设为左子树转换的双链表的第一个结点 然后把其父结点链在其右边,设置lef....

, , ,

剑指Offer之十九--二叉树的镜像

2016-03-27 20:13:41 huayonglun
0  评论    217  浏览

二叉树结构 class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } 题目描述 请完成一个函数,输入一个二叉树,输出它的镜像 二叉树镜像定义 源二叉树 镜像二叉树 解析 先序遍历给定树的每个结点 若遍历到的结点有子节点,就交换它的两个子结点 当交换完所有非叶子结点的左右子节点之后,就得到了树的镜像 递归实现 public void mirror(TreeNode root) { if(root == null || (root.left == null && root.right == null)){ return ; } TreeNode temp = root.left; root.left = root.right; root.right = temp; if(root.left != null){ mirror(root.left); } if(root.right....

, , ,
TOP