- 浏览: 173168 次
- 性别:
- 来自: 济南
文章分类
最新评论
与数组和链表相比,树的题目比它们要难一些,我们往往通过递归来处理树的题目,下面是对leetcode有关树操作的几道题目,包括找出树的所有路径,计算完全二叉树节点个数,二叉搜索树的最近公共祖先,普通二叉树的最近公共祖先。
1,Binary Tree Paths
给定一个二叉树,输出所有根节点到叶子节点的路径。
用深度优先遍历(DFS),依次保留搜索过的节点。代码如下:
2,Count Complete Tree Nodes
给定一个完全二叉树,计算树中节点的个数。
既然是完全二叉树,我们要好好利用它特有的性质,完全二叉树只有最后一层不满,并且节点是从左到右排列的。一个n层满二叉树的节点个数为2^n - 1,因此我们可以利用这些性质来处理这道题。代码如下:
3,Lowest Common Ancestor of a Binary Search Tree
给定一个二叉搜索树,查找两个节点的最近公共祖先。
不清楚公共祖先定义的查阅网上资料。二叉搜索树的性质是左子树的值都小于根节点值,右子树的值都大于根节点的值,我们可以通过值的比较来判断要查找的两个节点的位置,从而找到公共祖先。代码如下:
4,Lowest Common Ancestor of a Binary Tree
给定一个二叉树,找到两个节点的公共祖先。
与第三题不同,它是一个普通的二叉树,我们不能通过值来判断两个节点的位置,我们用深度优先搜索,通过返回值来判断两个节点的位置,代码如下:
1,Binary Tree Paths
给定一个二叉树,输出所有根节点到叶子节点的路径。
用深度优先遍历(DFS),依次保留搜索过的节点。代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> list = new LinkedList<String>(); if(root == null) return list; String str = String.valueOf(root.val); DFS(root, str, list); return list; } private void DFS(TreeNode root, String str, List<String> list) { if(root.left == null && root.right == null) list.add(str); if(root.left != null) DFS(root.left, str + "->" + root.left.val, list); if(root.right != null) DFS(root.right, str + "->" + root.right.val, list); } }
2,Count Complete Tree Nodes
给定一个完全二叉树,计算树中节点的个数。
既然是完全二叉树,我们要好好利用它特有的性质,完全二叉树只有最后一层不满,并且节点是从左到右排列的。一个n层满二叉树的节点个数为2^n - 1,因此我们可以利用这些性质来处理这道题。代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int countNodes(TreeNode root) { if(root == null) return 0; int leftnode = -1; int rightnode = -1; return countNodes(root, leftnode, rightnode); } private int countNodes(TreeNode root, int leftnode, int rightnode){ if(leftnode == -1) { TreeNode cur = root; while(cur != null) { leftnode ++; cur = cur.left; } } if(rightnode == -1) { TreeNode cur = root; while(cur != null) { rightnode ++; cur = cur.right; } } if(leftnode == rightnode) return (1 << leftnode) - 1; return 1 + countNodes(root.left, leftnode -1, -1) + countNodes(root.right, -1, rightnode -1); } }
3,Lowest Common Ancestor of a Binary Search Tree
给定一个二叉搜索树,查找两个节点的最近公共祖先。
不清楚公共祖先定义的查阅网上资料。二叉搜索树的性质是左子树的值都小于根节点值,右子树的值都大于根节点的值,我们可以通过值的比较来判断要查找的两个节点的位置,从而找到公共祖先。代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || root == p || root == q) return root; if(p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q); if(p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q); return root; } }
4,Lowest Common Ancestor of a Binary Tree
给定一个二叉树,找到两个节点的公共祖先。
与第三题不同,它是一个普通的二叉树,我们不能通过值来判断两个节点的位置,我们用深度优先搜索,通过返回值来判断两个节点的位置,代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if(left != null && right != null) return root; if(left == null) return right; return left; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 224Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 222You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 330Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 427Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 425The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 383Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 514Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 879Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 552Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 598Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 761Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 731You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ...
相关推荐
leetcode的题目:Balanced Binary Tree
题目二叉树所有路径题解* Definition for a binary tree node.* function TreeNode(val) {* @para
leetcode伪代码merge-two-binary-tree 题目解读: 题目来源: 原文: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the...
AlgoHub囊括了 POJ, ZOJ, leetcode, HackerRank 等网站的经典题目(一些质量不高的题目则忽略),且 AlgoHub有非常简单的加题系统,用户不需要写一行代码即可自己添加题目,所以AlgoHub的题库还在飞速增长中。...
leetcode 数据结构题目中的答案,已经调试,直接运行,求二叉树的最小深度
二叉树的直径(diameter-of-binary-tree) 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 ...
leetcode做过的LeetCode的题目记录一下。对一些比较经典的题型进行分类总结。... Binary Tree Right Side View【2020-01-15】130. Surrounded Regions【2020-01-09】114. Flatten Binary Tree to Linked List
2013湘潭大学邀请赛题目 Alice and Bob Binary Search Tree Coins DNA Edges of Triangle Five Tiger Goddess Hurry Up I Love Military Chess Jack’s sequence
题目地址:思路后序遍历左 - 右 - 根代码* Definition for a binary tree node.* function TreeNode(va
示例:返回它的最小深度 2.Related Topics树深度优先搜索广度优先搜索题目代码* Definition for a binary tree nod
题目链接: https://leetcode-cn.com/problems/binary-tree-right-side-view/ 解题思路: 树的层序遍历,先放左节点,再放右节点 每次将一层都放完的时候,将最后一个放入的元素加入到结果集中,其余直接清空 然后...
那么我们可以总结出一个senario: 处理左子树 添加自己的val值 处理右子树 95题 Unique BST II 我们可以构造一个递归函数,然后返回BST。我们需要传入的值是一个开始点,一个结束点。递归出口是当开始点大于结束点时...
construct-binary-tree-from-preorder-and-inorder-traversal 无官方题解 106 construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-right-pointers-in-eac
题目地址:思路这个题简单,使用二叉树,先循环左边的,再循环右边的,递归思想代码* Definition for a binary tree node.* fun
Binary Tree 题号 难度 题目名称及解答 C++ Java Python 中等 中等 中等 104 简单 105 中等 111 简单 144 中等 226 简单 230 中等 236 中等 297 困难 429 简单 589 简单 590 简单 实战题目 - 分治 题号 难度 题目...
##正好看见LeetCode可以刷Swift的题目 开始慢慢刷 swift有playground 做起来还是相当方便的 已完成题目 ----2016.9.30 两数循环 1. Two Sum 两数相加 2. Add Two Numbers 链表翻转 61. Rotate List 最大不同 318. ...
struct BinaryTreeNode // a node in the binary tree { int m_nValue; // value of node BinaryTreeNode *m_pLeft; // left child of node BinaryTreeNode *m_pRight; // right child of node };
命名,还包含部分题目需要的数据结构,例如:BinaryTree(二叉树)、Node (链表)。 我的运行环境: 编译器:Intelli IDEA (你只要能跑起 Java 程序就好了,别的都不重要) Java 版本:1.8 (不同版本对我项目的...
总结 (基于Python3) 面试题目主要考察 数据结构 (Data Structure),算法 (Algorithm),以及套路 (Pattern) 资源 刷题 一开始先忽略 hard 题,实习面试一般考 medium/easy 题,全职面试可能考 hard 题 每个 topic ...
binary tree b. hash table c. stack 6.一个二叉树的三种遍历方法的输出结果 7.链表按升序打印每打印完一个节点就将该节点从链表中删除 8.选择一种算法来整理出一个链接表。你为什么要选择这种方法?现在用...