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

白色蜗牛的互联网心得

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

标签: 二叉树 (4)

剑指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-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