【前言】
最近复习二叉树相关习题 ，根据课件练习几道基础习题 分享给大家
树是数据结构中的重中之重，尤其以各类二叉树基础问题为重要点，希望通过总结二叉树基础问题来深入了解二叉树。
【 二叉树概念简介 】
结点的度 ：一个结点含有子树的个数称为该结点的度； 树的度 ：一棵树中，所有结点度的最大值称为树的度； 叶子结点或终端结点 ：度为 0 的结点称为叶结点； 双亲结点或父结点 ：若一个结点含有子结点，则这个结点称为其子结点的父结点； 孩子结点或子结点 ：一个结点含有的子树的根结点称为该结点的子结点； 根结点 ：一棵树中，没有双亲结点的结点； 结点的层次 ：从根开始定义起，根为第 1层，根的子结点为第2层，以此类推 树的高度或深度 ：树中结点的最大层次；【二叉树性质】
1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 (2^(i -1))(i>0)个结点 2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^k-1(k>=0) 3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1 4. 具有n个结点的完全二叉树的深度k为 log(n+1) 上取整
【二叉树基础知识】
【 获得树的节点个数】int size(Node root){//获得树的节点个数
int count = 0;
if(root == null){
return 0;
}
count ++;
size( root.left);
size( root.right);
return count;
}
【获得叶子节点个数】
static leafcount = 0;
void getLeafNodeCount(TreeNode root){
if(root == null) return ;
if(root.left == null && root.right == null){
leafcount ++;
}
getLeafNodeCount( root.left);
getLeafNodeCount( root.right);
}【// 获取第K层节点的个数 】
int getKLevelNodeCount(Node root， int k){
if(root == null || k < 0) return -1;
if(k == 1){
return 1;
}
return getKLevelNodeCount(root.left，k-1) + getKLevelNodeCount(root.right， k-1);
}int getHeight(Node root){
if(root == null) return 0;//
int high1 = getHeight( root.left);//递归树的左边 计算高度
int high2 = getHeight(root.right);//递归树的右边 计算高度
if(high1 > high2) {
return high1 + 1;//返回时加上根节点
}else{
return high2 + 1;
}
TreeNode find(Node root, int val){//检测值是否存在
if(root == null) return null;
if(root.val = val) return root;
TreeNode val1 = find( root.left, val)
if( val1!= null){
return val1
}
TreeNode val2 = find( root.right, val);
if(val2 != null){
return val2;
}
return null; public boolean isBalanced(TreeNode root) {
return high(root) > 0;
}
public int high( TreeNode root1 ){
if(root1 == null ) return 1;
int high1 = high(root1.left );//递归出树的左数高度
int high2 = high(root1.right);// 右树高度
if(high1 == -1 || high2 == -1 || Math.abs(high1-high2 ) >1){//-1指遇到null是会返回-1 表明没有下个节点
return -1;
}else{
return Math.max(high1,high2)+1;
} public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;//p和q 同时为null时表明 递归结束 结点个数相同
if(p == null || q == null) return false;// 两者只有一个为null 另一个还没有走完 返回false
if(p.val != q.val ) return false;//比较两者的值
return isSameTree(p.left, q.left) && isSameTree( p.right, q.right) ; //同时递归树的左边和右边
public boolean isSameTree(TreeNode p, TreeNode q) {//判断其是否和其子树相同 和上一个判断相同的树一致
if(p == null && q == null) return true;
if(p == null || q == null) return false;
if(p.val != q.val ) return false;
return isSameTree(p.left, q.left) && isSameTree( p.right, q.right) ;
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null || subRoot == root){
return false;
}
if(isSameTree(root,subRoot)){//判断根节点相同
return true;
}
if (isSubtree(root.left,subRoot )){//递归树的左侧是否与子树相同
return true;
}
if(isSubtree(root.right,subRoot )){//递归树的右侧是否与子树相同
return true;
}
return false;
}class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int high1 = maxDepth(root.left);//递归左侧 求出高度
int high2 = maxDepth(root.right);//递归右侧 求出高度
if(high1 > high2){两者进行比较 大的一方加上起初根节点 返回
return high1+1;
}else{
return high2+1;
}
}
}class Solution {
public boolean isBalanced(TreeNode root) {
return high(root) > 0;
}
public int high( TreeNode root1 ){
if(root1 == null ) return 1;
int high1 = high(root1.left );//获取左树高度
int high2 = high(root1.right);//获取右树高度
if(high1 == -1 || high2 == -1 || Math.abs(high1-high2 ) >1){
return -1;
}else{
return Math.max(high1,high2)+1;//
}
}
}class Solution {
public boolean isSymmetric(TreeNode root) {
return issame( root, root);
}
public boolean issame(TreeNode root1,TreeNode root2){//
if(root1 == null && root2 == null) return true; 当两个根节点都为null 说明都到了最后一个节点
if(root1 == null || root2 == null) return false;//只有其中一个节点到达null
return root1.val == root2.val && issame( root1.left, root2.right) && issame( root1.right, root2.left);// 同时递归 因为是对称 左右要分开
}
}import java.util.*;
class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode (char val){
this.val = val;
}
}
public class Main{
public static int i = 0;
public static TreeNode createTree(String str) {
TreeNode root = null;
if(str.charAt(i) != '#') {
root = new TreeNode(str.charAt(i));
i++;
root.left = createTree(str);
root.right = createTree(str);
}else {
i++;
}
return root;
}
public static void inorder(TreeNode root) {
if(root == null) return ;
inorder(root.left);
System.out.print(root.val+" ");
inorder(root.right);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String str = in.nextLine();
TreeNode root = createTree(str);
inorder(root);
}
}
}class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();//定义一个链表进行存储
Queue<TreeNode> myqueue = new LinkedList<>();//栈里存放元素
if(root == null) return ret;
myqueue.offer(root);//将根节点放入栈中
while(!myqueue.isEmpty()){
List<Integer> list = new LinkedList<>();
int size = myqueue.size();//计算出此时栈中的元素个数
while(size != 0){
TreeNode cur = myqueue.poll();
list.add(cur.val);将栈中最顶上一个元素 放入 链表中
if(cur.left != null){这里分为两个情况
myqueue.offer(cur.left);
}
if(cur.right != null){
myqueue.offer(cur.right);
}
size--;
}
ret.add(list);
}
return ret;
}
}class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
Stack<TreeNode> stack1 = new Stack<>();
getPath( root, p, stack1);
Stack<TreeNode> stack2 = new Stack<>();
getPath( root,q, stack2);
int size1 = stack1.size();
int size2 = stack2.size();
if(size1 > size2){
int size = size1-size2;
while(size != 0){
stack1.pop();
size--;
}
while(!stack1.empty() && !stack2.empty()){
if(stack1.peek() == stack2.peek()){
return stack1.pop();
}else{
stack1.pop();
stack2.pop();
}
}
}else{
int size = size2-size1;
while(size != 0){
stack2.pop();
size--;
}
while(!stack1.empty() && !stack2.empty()){
if(stack1.peek() == stack2.peek()){
return stack1.pop();
}else{
stack1.pop();
stack2.pop();
}/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode pre = null;
public void inorder(TreeNode pCur) {
if(pCur == null) return ;
inorder(pCur.left);
pCur.left = pre;
if(pre != null){
pre.right = pCur;
}
pre = pCur;
inorder(pCur.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) return null;
inorder(pRootOfTree);
TreeNode head = pRootOfTree;
while(head.left != null){
head = head.left;
}
return head;
}
}class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> mylist = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while( cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
// System.out.println(cur);
mylist.add(cur.val);
cur = cur.left;
}
TreeNode pre = stack.pop();
cur = pre.right;
}
return mylist;
}
}/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> mylist = new ArrayList<Integer>();//
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while( cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);将根节点存放在 栈中
cur = cur.left;//将cur定义为左侧树
}
TreeNode pre = stack.pop();
mylist.add(pre.val);
cur = pre.right;将cur定义为右侧树
}
return mylist;
}
}/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> mylist = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode top = null;
while( cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
// System.out.println(cur);
cur = cur.left;
}
TreeNode pre = stack.peek();
//mylist.add(pre.val);
if(pre.right == null || pre.right == top){
TreeNode pres = stack.pop();
mylist.add(pres.val);
top = pre;
}else{
cur = pre.right;
}
}
return mylist;
}
}