销售网站建设推广,网站建设心得500字,企业信用信息公开网查询系统,专业网站建设首选公司#x1f320;作者#xff1a;TheMythWS. #x1f387;座右铭#xff1a;不走心的努力都是在敷衍自己#xff0c;让自己所做的选择#xff0c;熠熠发光。 目录
树形结构
概念
树的示意图
树的基本术语
树的表示
树的应用
二叉树(重点)
二叉树的定义
二叉树的五… 作者TheMythWS. 座右铭不走心的努力都是在敷衍自己让自己所做的选择熠熠发光。 目录
树形结构
概念
树的示意图
树的基本术语
树的表示
树的应用
二叉树(重点)
二叉树的定义
二叉树的五种不同形态
两种特殊的二叉树
二叉树的性质(重点!!!)
练习题
二叉树的存储
二叉树的基本操作
二叉树的遍历概念理解 (Traversing Binary Tree) )
1.先序遍历(DLR)
2.中序遍历(LDR)
3.后序遍历(LRD)
练习题一
4.层序遍历
练习题二
递归实现-先序中序后序遍历
非递归实现-先序中序后序遍历:
获取树中结点的个数
获取叶子结点(度为0的结点)的个数
获取第K层结点的个数
获取二叉树的高度
检测值为value的元素是否存在
层序遍历
判断一棵树是不是完全二叉树
OJ练习题 树形结构
概念 树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 它具有以下的特点 有一个特殊的结点称为根(root)结点根结点没有直接前驱结点, 只有后继结点.除根结点外其余结点被分成M(M 0)个互不相交的集合T1、T2、......、Tm其中每一个集合Ti (1 i m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个直接后继树是递归定义的。 树的示意图 注意树形结构中子树之间不能有交集否则就不是树形结构 树的基本术语 结点的度一个结点含有子树的个数称为该结点的度 如上图A的度为6树的度(唯一性)一棵树中所有结点度的最大值称为树的度 如上图树的度为6叶子结点或终端结点度为0的结点称为叶子结点 如上图B、C、H、I...等结点点为叶子结点双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点根结点一棵树中没有双亲结点的结点如上图A结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次 如上图树的高度为4 树的以下概念只需了解只要知道是什么意思即可非终端结点或分支结点度不为0的结点 如上图D、E、F、G...等节点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为堂兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙有序树与无序树:若一棵树中所有子树从左到右的排序是有顺序的不能颠倒次序称该树为有序树反之称为无序树。 森林由mm0棵互不相交的树组成的集合称为森林 树的表示 class Node {int value; // 树中存储的数据Node firstChild; // 第一个孩子引用Node nextBrother; // 下一个兄弟引用
} 树的应用
文件系统管理目录和文件 二叉树(重点)
二叉树的定义
一棵二叉树是结点的一个有限集合该集合 1. 或者为空 2. 或者是由一个根结点加上两棵别称为左子树和右子树的互不相交的二叉树组成。 特点 1 每个结点的度≤2 2 是有序树 说明 二叉树的特点是每个结点最多有两个孩子 或者说 在二叉树中 不存在度大于2的结点 并且二叉树是有序树 树为无序树, 其子树的顺序不能颠倒。 二叉树的五种不同形态 两种特殊的二叉树 1. 满二叉树: 一棵二叉树如果每层的结点数都达到最大值则这棵二叉树就是满二叉树。也就是说如果一棵二叉树的层数为K且结点总数是2^k - 1则它就是满二叉树。2. 完全二叉树: 完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。 二叉树的性质(重点!!!) 练习题 1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数n0为 A 不存在这样的二叉树B 200 C 198 D 199 n0 n2 1 200 2.在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2 3.一个具有767个结点的完全二叉树其叶子结点个数为 A 383B 384 C 385 D 386奇数个结点的完全二叉树说明没有度为1的结点, 则767 n0 n2, n0 n2 1, n2 n0 - 1, 767 2n0 - 1, n0 384. 4.一棵完全二叉树的结点数为531个那么这棵树的高度为 A 11 B 10 C 8 D 12 二叉树的存储
顺序存储结构数组表示 链式存储结构指针表示 二叉树的链式存储是通过一个一个的结点引用起来的常见的表示方式有二叉和三叉表示方式具体如下
// 孩子表示法
class Node {int val; // 数据域Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {int val; // 数据域Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树Node parent; // 当前结点的根结点
}
二叉树的基本操作 前置说明 此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。 public class BinaryTree {public static class BTNode {BTNode left;BTNode right;int value;BTNode(int value) {this.value value;}}private BTNode root;public void createBinaryTree() {BTNode node1 new BTNode(1);BTNode node2 new BTNode(2);BTNode node3 new BTNode(3);BTNode node4 new BTNode(4);BTNode node5 new BTNode(5);BTNode node6 new BTNode(6);root node1;node1.left node2;node2.left node3;node1.right node4;node4.left node5;node5.right node6;}public static void main(String[] args) {BinaryTree binaryTree new BinaryTree();binaryTree.createBinaryTree();}
} 注意上述代码并不是创建二叉树的方式真正创建二叉树方式后序详解重点讲解. 从概念中可以看出二叉树定义是递归式的因此后序基本操作中基本都是按照该概念实现的。 二叉树的遍历概念理解 (Traversing Binary Tree) )
1.先序遍历(DLR) 2.中序遍历(LDR) 3.后序遍历(LRD) 练习题一 问题1如何可唯一地确定一棵二叉树 答:先序(找根)中序(找位置) 或 后序(找根)中序(找位置)均可唯一地确定一棵二叉树先序 后序(X) 问题2二叉树的二叉链表存储结构中有多少个指针域未利用? 答:二叉树的二叉链表存储结构中假如有n个结点, 则共有2n个指针域(定义的) 已经使用的有n-1个指针域所以有2n - (n - 1) n1个指针域未利用. 为什么是n - 1?(因为减去了一个根结点, 根结点是没有被指向的, 有n个结点除了根结点, 孩子结点就是n-1个) 4.层序遍历
设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 总结: 学习二叉树结构最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一是二叉树上进行其它运算之基础。 在遍历二叉树时如果没有进行某种约定每个人都按照自己的方式遍历得出的结果就比较混乱如果按照某种规则进行约定则每个人对于同一棵树的遍历结果肯定是相同的。 如果D代表根结点L代表根结点的左子树R代表根结点的右子树则根据遍历根结点的先后次序有以下遍历方式 DLR前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点---根的左子树---根的右子树。LDR中序遍历(Inorder Traversal)——根的左子树---根节点---根的右子树。LRD后序遍历(Postorder Traversal)——根的左子树---根的右子树---根结点。 分析前序递归遍历中序与后序图解类似 前序遍历结果1 2 3 4 5 6 中序遍历结果3 2 1 5 4 6 后序遍历结果3 2 5 6 4 1 练习题二 1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为()A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA 2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为()A: E B: F C: G D: H 3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为() A: adbce B: decab C: debac D: abcde 4.某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出(同一层从左到右)的序列为()A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF 递归实现-先序中序后序遍历
我们先基于以下二叉树结构来实现 public class TestBinaryTree {static class TreeNode {public char val;//数据域public TreeNode left;//左孩子的引用public TreeNode right;//右孩子的引用public TreeNode(char val) {this.val val;}}//public TreeNode root;//二叉树的根结点public TreeNode createTree() {TreeNode A new TreeNode(A);TreeNode B new TreeNode(B);TreeNode C new TreeNode(C);TreeNode D new TreeNode(D);TreeNode E new TreeNode(E);TreeNode F new TreeNode(F);TreeNode G new TreeNode(G);TreeNode H new TreeNode(H);A.left B;A.right C;B.left D;B.right E;C.left F;C.right G;E.right H;//this.root A;return A;}// 前序遍历void preOrder(TreeNode root) {if (root null) {return;}System.out.print(root.val );preOrder(root.left);preOrder(root.right);}// 中序遍历void inOrder(TreeNode root) {if (root null) {return;}inOrder(root.left);System.out.print(root.val );inOrder(root.right);}// 后序遍历void postOrder(TreeNode root) {if (root null) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val );}
}
public class Test {public static void main(String[] args) {TestBinaryTree testBinaryTree new TestBinaryTree();TestBinaryTree.TreeNode root testBinaryTree.createTree();testBinaryTree.preOrder(root);System.out.println();testBinaryTree.inOrder(root);System.out.println();testBinaryTree.postOrder(root);}
} 非递归实现-先序中序后序遍历:
此次我们对二叉树结构做了微调 先序图解 中序图解 后序图解 (直接修改创建二叉的代码)
public TreeNode createTree2() {TreeNode A new TreeNode(A);TreeNode B new TreeNode(B);TreeNode C new TreeNode(C);TreeNode D new TreeNode(D);TreeNode E new TreeNode(E);TreeNode F new TreeNode(F);TreeNode G new TreeNode(G);TreeNode H new TreeNode(H);A.left B;A.right C;B.left D;B.right E;C.left F;C.right G;//E.right H;//this.root A;return A;}//非递归实现前序遍历:public void preOrderNor(TreeNode root) {if (root null) {return;}TreeNode cur root;DequeTreeNode stack new ArrayDeque();while (cur ! null || !stack.isEmpty()) {//如果cur null stack null 说明已经遍历完了.while (cur ! null) {stack.push(cur);System.out.print(cur.val );cur cur.left;}//左边为空, 弹出栈顶的元素TreeNode top stack.pop();cur top.right;/*如果右边为空, 最外层的while循环也进入不了,但是如果此时栈内还有元素, 也可以进入最外层while循环, 但是不能进入最内层while循环然后弹出栈顶的元素*///如果右边不为空, 循环也可以进入, 将新的元素压栈}}//非递归实现中序遍历:public void inOrderNor(TreeNode root) {if (root null) {return;}TreeNode cur root;DequeTreeNode stack new ArrayDeque();while (cur ! null || !stack.isEmpty()) {//如果cur null stack null 说明已经遍历完了.while (cur ! null) {stack.push(cur);cur cur.left;}//左边为空, 弹出栈顶的元素TreeNode top stack.pop();System.out.print(top.val );cur top.right;/*如果右边为空, 最外层的while循环也进入不了,但是如果此时栈内还有元素, 也可以进入最外层while循环, 但是不能进入最内层while循环然后弹出栈顶的元素*///如果右边不为空, 循环也可以进入, 将新的元素压栈}}//非递归实现后序遍历:public void postOrderNor(TreeNode root) {if (root null) {return;}TreeNode cur root;TreeNode prev null;//这个引用用来记录已经打印过的节点DequeTreeNode stack new ArrayDeque();while (cur ! null || !stack.isEmpty()) {//如果cur null stack null 说明已经遍历完了.while (cur ! null) {stack.push(cur);cur cur.left;}//左边为空, 查看栈顶的元素TreeNode top stack.peek();if (top.right null || top.right prev) {//如果栈顶元素的右边为空或者栈顶元素的右边已经打印过---直接打印 弹出这个栈顶元素不需要要再往后遍历不然会重复打印顺便记录刚刚这个栈顶元素也被打印过了下次也不要打印它了System.out.print(top.val );stack.pop();prev top;} else {cur top.right;}/*如果右边为空, 最外层的while循环也进入不了,但是如果此时栈内还有元素, 也可以进入最外层while循环, 但是不能进入最内层while循环然后查看栈顶的元素, 再判断.*///如果右边不为空, 循环也可以进入, 将新的元素压栈}}
public static void main(String[] args) {TestBinaryTree testBinaryTree new TestBinaryTree();TestBinaryTree.TreeNode root testBinaryTree.createTree2();testBinaryTree.preOrderNor(root);System.out.println();testBinaryTree.inOrderNor(root);System.out.println();testBinaryTree.postOrderNor(root);} 接下来我们用以下二叉树结构进行其它操作 获取树中结点的个数 // 获取树中结点的个数// 时间复杂度:O(N)// 空间复杂度:O(logN)满二叉树的情况, 相当于树的高度 ~ O(N)单分支树的情况.int size(TreeNode root) {//子问题思路(左子树结点 右子树结点 1) 建议写法!if (root null) {return 0;}int leftSize size(root.left);int rightSize size(root.right);return leftSize rightSize 1;}public static int nodeSize;//注意这儿有问题, 在OJ上如果有两个树对象测试结点个数, 那么会测试出来的结点个数相同, 因为它们共用nodeSize了.public void size2(TreeNode root) {//遍历思路(遇到结点就 1)if (root null) {return;}nodeSize;size2(root.left);size2(root.right);}
public class Test {public static void main(String[] args) {TestBinaryTree testBinaryTree new TestBinaryTree();TestBinaryTree.TreeNode root testBinaryTree.createTree();System.out.println((size1方法)结点个数: testBinaryTree.size(root));//8testBinaryTree.size2(root);int nodeSize TestBinaryTree.nodeSize;System.out.println((size2方法)结点个数: nodeSize);//8System.out.println(----------------);TestBinaryTree testBinaryTree2 new TestBinaryTree();TestBinaryTree.TreeNode root2 testBinaryTree2.createTree();System.out.println((size1方法)结点个数: testBinaryTree.size(root));//8testBinaryTree.size2(root);int nodeSize2 TestBinaryTree.nodeSize;System.out.println((size2方法)结点个数: nodeSize2);//16, 结果有问题, 是因为nodeSize是静态变量, 新建一棵树对象会共用nodeSize, 所以遍历出来的结点个数有问题.}
} 获取叶子结点(度为0的结点)的个数 // 获取叶子结点的个数// 子问题:左子树的叶子结点 右子树的叶子结点int getLeafNodeCount(TreeNode root) {if (root null) {return 0;}if (root.left null root.right null) {//遇到叶子结点了.return 1;}int leftSize getLeafNodeCount(root.left);int rightSize getLeafNodeCount(root.right);return leftSize rightSize;}public int leafSize;// 遍历思路:遇到叶子结点就 1public void getLeafNodeCount2(TreeNode root) {if (root null) {return;}if (root.left null root.right null) {//遇到叶子结点了.leafSize;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);}
public class Test {public static void main(String[] args) {TestBinaryTree testBinaryTree new TestBinaryTree();TestBinaryTree.TreeNode root testBinaryTree.createTree();System.out.println(叶子结点的个数: testBinaryTree.getLeafNodeCount(root));testBinaryTree.getLeafNodeCount2(root);System.out.println(叶子结点的个数: testBinaryTree.leafSize);}
} 获取第K层结点的个数 // 获取第K层结点的个数int getKLevelNodeCount(TreeNode root, int k) {if (root null) {return 0;}if (k 1) {return 1;}int leftSize getKLevelNodeCount(root.left, k - 1);int rightSize getKLevelNodeCount(root.right, k - 1);return leftSize rightSize;}
public class Test {public static void main(String[] args) {TestBinaryTree testBinaryTree new TestBinaryTree();TestBinaryTree.TreeNode root testBinaryTree.createTree();System.out.println(第k层的结点个数: testBinaryTree.getKLevelNodeCount(root, 3));}
} 获取二叉树的高度 // 获取二叉树的高度// 时间复杂度O(N), 因为每一个结点都会被访问// 空间复杂度O(树的高度)public int getHeight(TreeNode root) {if (root null) {return 0;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return (leftHeight rightHeight ? leftHeight : rightHeight) 1;}
public class Test {public static void main(String[] args) {TestBinaryTree testBinaryTree new TestBinaryTree();TestBinaryTree.TreeNode root testBinaryTree.createTree();System.out.println(树的高度: testBinaryTree.getHeight(root));}
} 检测值为value的元素是否存在 // 检测值为value的元素是否存在public TreeNode find(TreeNode root, int val) {if (root null) {return null;}if (root.val val) {return root;}TreeNode leftTree find(root.left, val);if (leftTree ! null) {//左子树找return leftTree;}TreeNode rightTree find(root.right, val);if (rightTree ! null) {//右子树找return rightTree;}return null;//都没找到}
public class Test {public static void main(String[] args) {TestBinaryTree testBinaryTree new TestBinaryTree();TestBinaryTree.TreeNode root testBinaryTree.createTree();TestBinaryTree.TreeNode E testBinaryTree.find(root, E);if (E ! null){System.out.println(查找到了E元素, 且E的值为: E.val);} else {System.out.println(没有此元素!);}TestBinaryTree.TreeNode J testBinaryTree.find(root, J);if (J ! null){System.out.println(查找到了J元素, 且J的值为: J.val);} else {System.out.println(没有此元素!);}}
} 层序遍历 //层序遍历(不带返回值)public void levelOrder(TreeNode root) {if (root null) {return;}QueueTreeNode queue new LinkedList();//先将头结点入队queue.offer(root);while (!queue.isEmpty()) {//队列不为空//出队的同时用cur记录出队的结点, 同时打印出队结点的valueTreeNode cur queue.poll();System.out.print(cur.val );//如果cur的左子树和右子树有结点就入队if (cur.left ! null) {queue.offer(cur.left);}if (cur.right ! null) {queue.offer(cur.right);}}}public class Test {public static void main(String[] args) {TestBinaryTree testBinaryTree new TestBinaryTree();TestBinaryTree.TreeNode root testBinaryTree.createTree();testBinaryTree.levelOrder(root);}
} 判断一棵树是不是完全二叉树 boolean isCompleteTree(TreeNode root){if (root null) {return true;}QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {TreeNode cur queue.poll();if (cur ! null) {queue.offer(cur.left);queue.offer(cur.right);} else {break;}}//走到这儿说明cur nullwhile (!queue.isEmpty()) {TreeNode tmp queue.poll();if (tmp ! null) {//队列里剩余的元素不全是null, 说明不是完全二叉树return false;}}return true;}
OJ练习题
1. 检查两颗树是否相同。 /*** 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 {//检查两棵树是否相同//时间复杂度和空间复杂度: O(min(m, n)) m 和 n是结点的个数//如果一颗树的结点多 一颗树的结点少 必然是不相等的, 所以只需要遍历完结点少的树就行了, 不需要去遍历剩下的结点.//如果两个树的结点一样, min(m, n) 结果都一样, 大不了最坏情况就O(n)public boolean isSameTree(TreeNode p, TreeNode q) {if (p null q ! null || p ! null q null) {return false;}//走到这里 要么都是空 要么都不是空if (p null q null) {//都是空return true;}if (p.val ! q.val) {//都不是空, 在判断值是否相等return false;}//p q都不是空, 且值一样, 当前只是判断了根结点是否相同, 所以下面还要进行递归判断左子树和右子树是否一样.return isSameTree(p.left, q.left) isSameTree(p.right, q.right);}
}
2.另一颗树的子树。 /*** 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 {//时间复杂度:O(S * T) 对于S上的每一个点都需要做一次深度优先搜索来和T匹配, 匹配一次的时间复杂度是O(T)//空间复杂度:O(max(ds, dt)), ds 和 dt分别代表两棵树的深度public boolean isSubtree(TreeNode root, TreeNode subRoot) {if (root null) {return false;}if (isSameTree(root, subRoot)) {return true;}if (isSubtree(root.left, subRoot)) {return true;}if (isSubtree(root.right, subRoot)) {return true;}return false;}//检查两棵树是否相同//时间复杂度和空间复杂度: O(min(m, n)) m 和 n是结点的个数//如果一颗树的结点多 一颗树的结点少 必然是不相等的, 所以只需要遍历完结点少的树就行了, 不需要去遍历剩下的结点.//如果两个树的结点一样, min(m, n) 结果都一样, 大不了最坏情况就O(n)public boolean isSameTree(TreeNode p, TreeNode q) {if (p null q ! null || p ! null q null) {return false;}//走到这里 要么都是空 要么都不是空if (p null q null) {//都是空return true;}if (p.val ! q.val) {//都不是空, 在判断值是否相等return false;}//p q都不是空, 且值一样, 当前只是判断了根结点是否相同, 所以下面还要进行递归判断左子树和右子树是否一样.return isSameTree(p.left, q.left) isSameTree(p.right, q.right);}
}
3. 翻转二叉树。 /*** 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 TreeNode invertTree(TreeNode root) {if (root null) {return null;}//方法1:利用临时结点来存储要交换的结点值
// TreeNode tmpNode root.left;
// root.left root.right;
// root.right tmpNode;
// //递归进行翻转
// invertTree(root.left);
// invertTree(root.right);//方法2:利用返回值TreeNode left invertTree(root.left);TreeNode right invertTree(root.right);//翻转root.left right;root.right left;return root;}
}
4. 判断一颗二叉树是否是平衡二叉树。 /*** 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 boolean isBalanced1(TreeNode root) {if (root null) {return true;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return Math.abs(leftHeight - rightHeight) 2 isBalanced1(root.left) isBalanced1(root.right);}// 获取二叉树的高度// 时间复杂度O(N), 因为每一个结点都会被访问// 空间复杂度O(树的高度)public int getHeight(TreeNode root) {if (root null) {return 0;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return (leftHeight rightHeight ? leftHeight : rightHeight) 1;}//时间复杂度O(N)public boolean isBalanced(TreeNode root) {//看返回的是否为正数, 如果是负数说明不平衡return getHeight2(root) 0;}// public int getHeight2(TreeNode root) {// if (root null) {// return 0;// }// int leftHeight getHeight2(root.left);// int rightHeight getHeight2(root.right);// if (leftHeight 0 rightHeight 0 // Math.abs(leftHeight - rightHeight) 1) {// //return (leftHeight rightHeight ? leftHeight : rightHeight) 1;// return Math.max(leftHeight, rightHeight) 1;// } else {//左子树和右子树的高度差超过了2// return -1;// }// }public int getHeight2(TreeNode root) {if (root null) {return 0;}int leftHeight getHeight2(root.left);if (leftHeight 0) {return -1;}int rightHeight getHeight2(root.right);if (rightHeight 0) {return -1;}if (Math.abs(leftHeight - rightHeight) 1) {//return (leftHeight rightHeight ? leftHeight : rightHeight) 1;return Math.max(leftHeight, rightHeight) 1;} else {//左子树和右子树的高度差超过了2return -1;}}
}
5. 对称二叉树。 /*** 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 boolean isSymmetric(TreeNode root) {if (root null) {return true;}return isSymmetricChild(root.left, root.right);}public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {if (leftTree ! null rightTree null || leftTree null rightTree ! null) {return false;}if (leftTree null rightTree null) {return true;}//走到这里说明左子树和右子树都不为空, 就需要先判断值是否一样if (leftTree.val ! rightTree.val) {return false;}//走到这里说明左子树和右子树不为空, 且值一样//再判断左子树的左子树和右子树的右子树是否相等, 左子树的右子树和右子树的左子树是否相等.return isSymmetricChild(leftTree.left, rightTree.right) isSymmetricChild(leftTree.right, rightTree.left);}
}
6. 二叉树的构建及遍历。 import java.util.Scanner;
class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str in.nextLine();TreeNode root createTree(str);inOrder(root);}}public static int i 0;//每次递归i的值要发生变化, 所以定义在递归函数的外面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);}
}
7. 二叉树的层序遍历 。 /*** 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 ListListInteger levelOrder(TreeNode root) {ListListInteger list new ArrayList();if(root null) {return list;}QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {//队列不为空, 记录当前的结点个数size(相当于每一层的结点), 然后出队size个结点, 然后添加到集合.int size queue.size();ListInteger tmp new ArrayList();while (size ! 0) {//出队size个结点TreeNode cur queue.poll();tmp.add(cur.val);size--;if (cur.left ! null) {queue.offer(cur.left);}if (cur.right ! null) {queue.offer(cur.right);}}list.add(tmp);}return list;}
}
8. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {//方法1:// public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// if (root null) {// return null;// }// //先判断根结点是不是其中的一个// if (root p || root q) {// return root;// }// //去左子树和右子树找是否有p, q// TreeNode leftRet lowestCommonAncestor(root.left, p, q);// TreeNode rightRet lowestCommonAncestor(root.right, p, q);// if (leftRet ! null rightRet ! null) {//左子树和右子树都找到了p和q// return root;// } else if (leftRet ! null) {//左子树找到的第一个p或者q, 就是公共祖先// return leftRet;// } else if (rightRet ! null) {//右子树找到的第一个p或者q, 就是公共祖先// return rightRet;// }// //左子树和右子树都没有找到// return null;// }//方法2:// 找到根节点到指定节点node路径上的所有的节点, 存放到栈中.public boolean getPath(TreeNode root, TreeNode node, DequeTreeNode stack) {if (root null || node null) {return false;}stack.push(root);//放完之后 要检查if (root node) {return true;}boolean ret1 getPath(root.left, node, stack);if (ret1) {//ret1 truereturn true;}boolean ret2 getPath(root.right, node, stack);if (ret2) {//ret2 truereturn true;}stack.pop();return false;}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//1.两个栈当中 存储好数据DequeTreeNode stack1 new ArrayDeque();getPath(root, p, stack1);DequeTreeNode stack2 new ArrayDeque();getPath(root, q, stack2);//2.判断栈的大小int size1 stack1.size();int size2 stack2.size();//哪个栈的元素多, 就要先出栈多出来的元素if (size1 size2) {int size size1 - size2;while (size ! 0) {stack1.pop();size--;}} else {int size size2 - size1;while (size ! 0) {stack2.pop();size--;}}//通过上述操作---栈里面的元素个数是一样的.while (!stack1.isEmpty() !stack2.isEmpty()) {if (stack1.peek() ! stack2.peek()) {stack1.pop();stack2.pop();} else {return stack1.peek();}}return null;}
}
9. 根据一棵树的前序遍历与中序遍历构造二叉树。 /*** 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 int i 0;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder, inorder, 0, inorder.length - 1);}//建立子树(每次先序遍历确定根的时候, 从中序遍历找位置确定根的左右子树)public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend) {if (inbegin inend) {//说明没有子树了.return null;}TreeNode root new TreeNode(preorder[i]);//每次放入先序遍历的节点//找到当前根, 然后根据中序遍历去确定此节点的位置int rootIndex findIndex(inorder, inbegin, inend, preorder[i]);i;//加完之后, 下次找的就不是根节点了.root.left buildTreeChild(preorder, inorder, inbegin, rootIndex - 1);root.right buildTreeChild(preorder, inorder, rootIndex 1, inend);return root;}//根据中序遍历, 确定根的位置private int findIndex(int[] inorder, int inbegin, int inend, int key){for (int i inbegin; i inend; i) {if (inorder[i] key) {return i;}}return -1;}
}
10. 根据一棵树的中序遍历与后序遍历构造二叉树。
/*** 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 int i 0;public TreeNode buildTree(int[] inorder, int[] postorder) {i postorder.length - 1;//从后往前找.return buildTreeChild(inorder, postorder, 0, inorder.length - 1);}//建立子树(每次后序遍历确定根的时候, 从中序遍历找位置确定根的左右子树)public TreeNode buildTreeChild(int[] inorder, int[] postorder, int inbegin, int inend) {if (inbegin inend) {//说明没有子树了.return null;}TreeNode root new TreeNode(postorder[i]);//每次放入后序遍历的节点//找到当前根, 然后根据中序遍历去确定此节点的位置int rootIndex findIndex(inorder, inbegin, inend, postorder[i]);i--;//减完之后, 下次找的就不是根节点了.//注意:这儿要先建立右树, 因为后序遍历是左 右 根.root.right buildTreeChild(inorder, postorder, rootIndex 1, inend);root.left buildTreeChild(inorder, postorder, inbegin, rootIndex - 1);return root;}//根据中序遍历, 确定根的位置private int findIndex(int[] inorder, int inbegin, int inend, int key) {for (int i inbegin; i inend; i) {if (inorder[i] key) {return i;}}return -1;}
}
11. 二叉树创建字符串。 /*** 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 String tree2str(TreeNode root) {if (root null) {return null;}StringBuilder stringBuilder new StringBuilder();tree2strChild(root, stringBuilder);return stringBuilder.toString();}public void tree2strChild(TreeNode t, StringBuilder stringBuilder) {if (t null) {return;}stringBuilder.append(t.val);//把根节点先加入if (t.left ! null) {//左边不为空stringBuilder.append(();tree2strChild(t.left, stringBuilder);//递归左边stringBuilder.append());} else {//左边为空if (t.right ! null) {//右边不为空stringBuilder.append(());} else {//右边为空return;}}if (t.right null) {//右边为空return;} else {//右边不为空stringBuilder.append(();tree2strChild(t.right, stringBuilder);//递归右边stringBuilder.append());}}
}
12. 二叉树前序非递归遍历实现 。
/*** 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 {//递归的写法:/*//不好的写法: 没利用返回值 (遍历思路, 遇到一个打印一个)ListInteger ret new ArrayList();public ListInteger preorderTraversal(TreeNode root) {//ListInteger ret new ArrayList();//这句话不能放在这儿, 因为每次递归ret都是新的值.所以要把ret提到函数外面if(root null) {return ret;}//System.out.print(root.val );ret.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return ret;}*//*//将就的写法:public ListInteger preorderTraversal(TreeNode root) {ListInteger ret new ArrayList();//这儿放到函数内是因为递归调用的不是本身的函数,不会让ret每次是新的值, 而是另一个函数func.func(root,ret);return ret;}public void func(TreeNode root,ListInteger ret) {//递归的函数if(root null) {return;}//System.out.print(root.val );ret.add(root.val);func(root.left,ret);func(root.right,ret);}*///子问题思路// public ListInteger preorderTraversal(TreeNode root) {// ListInteger ret new ArrayList();//如果非要写在这儿, 将每次递归的返回值, 加到ret中// if (root null) {// return ret;// }// ret.add(root.val);// ListInteger leftTree preorderTraversal(root.left);// ret.addAll(leftTree);//addAll(Collection? extends E c), 尾插c中的元素, 传入的参数是实现了collection接口且泛型类型Integer// ListInteger rightTree preorderTraversal(root.right);// ret.addAll(rightTree);// return ret;// }//非递归的写法:public ListInteger preorderTraversal(TreeNode root) {ListInteger ret new ArrayList();if (root null) {return ret;}TreeNode cur root;DequeTreeNode stack new ArrayDeque();while (cur ! null || !stack.isEmpty()) {//如果cur null stack null 说明已经遍历完了.while (cur ! null) {stack.push(cur);//System.out.print(cur.val );ret.add(cur.val);cur cur.left;}//左边为空, 弹出栈顶的元素TreeNode top stack.pop();cur top.right;/*如果右边为空, 最外层的while循环也进入不了,但是如果此时栈内还有元素, 也可以进入最外层while循环, 但是不能进入最内层while循环然后弹出栈顶的元素*///如果右边不为空, 循环也可以进入, 将新的元素压栈}return ret;}
}
13. 二叉树中序非递归遍历实现。
/*** 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 ListInteger inorderTraversal(TreeNode root) {// ListInteger ret new ArrayList();//如果非要写在这儿, 将每次递归的返回值, 加到ret中// if (root null) {// return ret;// }// ListInteger leftTree inorderTraversal(root.left);// ret.addAll(leftTree);//addAll(Collection? extends E c), 尾插c中的元素, 传入的参数是实现了collection接口且泛型类型Integer// ret.add(root.val);// ListInteger rightTree inorderTraversal(root.right);// ret.addAll(rightTree);// return ret;// }//非递归写法:public ListInteger inorderTraversal(TreeNode root) {ListInteger ret new ArrayList();if (root null) {return ret;}TreeNode cur root;DequeTreeNode stack new ArrayDeque();while (cur ! null || !stack.isEmpty()) {//如果cur null stack null 说明已经遍历完了.while (cur ! null) {stack.push(cur);cur cur.left;}//左边为空, 弹出栈顶的元素TreeNode top stack.pop();//System.out.print(cur.val );ret.add(top.val);cur top.right;/*如果右边为空, 最外层的while循环也进入不了,但是如果此时栈内还有元素, 也可以进入最外层while循环, 但是不能进入最内层while循环然后弹出栈顶的元素*///如果右边不为空, 循环也可以进入, 将新的元素压栈}return ret;}
}
14. 二叉树后序非递归遍历实现。
/*** 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 ListInteger postorderTraversal(TreeNode root) {// ListInteger ret new ArrayList();//如果非要写在这儿, 将每次递归的返回值, 加到ret中// if (root null) {// return ret;// }// ListInteger leftTree postorderTraversal(root.left);// ret.addAll(leftTree);//addAll(Collection? extends E c), 尾插c中的元素, 传入的参数是实现了collection接口且泛型类型Integer// ListInteger rightTree postorderTraversal(root.right);// ret.addAll(rightTree);// ret.add(root.val);// return ret;// }//非递归实现:public ListInteger postorderTraversal(TreeNode root) {ListInteger ret new ArrayList();if (root null) {return ret;}TreeNode cur root;TreeNode prev null;//这个引用用来记录已经打印过的节点DequeTreeNode stack new ArrayDeque();while (cur ! null || !stack.isEmpty()) {//如果cur null stack null 说明已经遍历完了.while (cur ! null) {stack.push(cur);cur cur.left;}//左边为空, 查看栈顶的元素TreeNode top stack.peek();if (top.right null || top.right prev) {//如果栈顶元素的右边为空或者栈顶元素的右边已经打印过---打印 弹出栈顶元素//System.out.print(top.val );ret.add(top.val);stack.pop();prev top;} else {cur top.right;}//如果右边为空, 最外层的while循环也进入不了,//但是如果此时栈内还有元素, 也可以进入最外层while循环, 但是不能进入最内层while循环//然后查看栈顶的元素, 再判断.//如果右边不为空, 循环也可以进入, 将新的元素压栈}return ret;}
}
15.二叉树的深度。
/*** 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 int maxDepth(TreeNode root) {if (root null) {return 0;}int leftHeight maxDepth(root.left);int rightHeight maxDepth(root.right);return (leftHeight rightHeight ? leftHeight : rightHeight) 1; }
}
