学习数据结构,二叉树是一大难点,也是一大重点,小伙伴们和我一起看看二叉树的知识吧! 本文代码是Java。
二叉树是指只有一个根节点并且只有两个孩子节点的树。
例如:
二叉树中有两种特殊的二叉树,分别是满二叉树和完全二叉树。
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。
2.完全 二叉树:
一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。
注意事项:
以该二叉树为例子:
前序遍历始终遵守 根节点 -> 左节点 -> 右节点的规律;
例如此二叉树通过前序遍历得出的顺序是:ADBCF.
递归版本:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
func(root);
return list;
}
List<Integer> list = new ArrayList<>();
public void func(TreeNode root){
if(root == null){
return;
}
list.add(root.val);
func(root.left);
func(root.right);
}
}
非递归版本:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode tmp = null;
while(!stack.empty() || root!=null){
while(root != null){
stack.push(root);
list.add(root.val);
root = root.left;
}
root = stack.pop();
root = root.right;
}
return list;
}
}
中序遍历始终遵守 左节点 -> 根节点 -> 右节点的规律;
例如此二叉树通过中序遍历得出的顺序是:DBAFC.
递归版本:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
func(root);
return list;
}
List<Integer> list = new ArrayList<>();
public void func(TreeNode root){
if(root == null){
return;
}
func(root.left);
list.add(root.val);
func(root.right);
}
}
非递归版本:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while(!stack.empty() || root!=null) {
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
list.add(root.val);
root = root.right;
}
return list;
}
}
后序遍历始终遵守 左节点 -> 右节点 -> 根节点 的规律;
例如此二叉树通过后序遍历得出的顺序是:BDFCA.
递归版本:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
func(root);
return list;
}
List<Integer> list = new ArrayList<>();
public void func(TreeNode root){
if(root == null){
return;
}
func(root.left);
func(root.right);
list.add(root.val);
}
}
非递归版本:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode tmp = null;
while(!stack.empty() || root != null){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == tmp) {
list.add(root.val);
tmp = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return list;
}
}
层序遍历始终遵守 从根节点开始遍历,一层一层往下遍历 的规律;
例如此二叉树通过层序遍历得出的顺序是:ADCBF.
代码:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> list = new LinkedList<>();
if(root != null){
queue.offer(root);
}
while(!queue.isEmpty()){
List<Integer> list1 = new LinkedList<>();
int size1 = queue.size();
while(size1-- > 0){
root = queue.poll();
list1.add(root.val);
if(root.left != null){
queue.offer(root.left);
}
if(root.right != null){
queue.offer(root.right);
}
}
list.add(list1);
}
return list;
}
}
105. 从前序与中序遍历序列构造二叉树 - 力扣(Leetcode)
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(inorder == null){
return null;
}
return buildTreeChild(preorder,inorder, 0, inorder.length-1);
}
int pre = 0;
public TreeNode buildTreeChild(int[] preorder, int[] inorder, int form, int end){
if(form > end) return null;
//if(pre >= preorder.length) return null;
TreeNode tmp = new TreeNode(preorder[pre]);
int i = findTree(inorder, preorder[pre],form,end);
pre++;
tmp.left = buildTreeChild(preorder,inorder, form, i-1);
tmp.right = buildTreeChild(preorder,inorder, i+1, end);
return tmp;
}
public int findTree(int[] inorder,int k, int index, int end) {
for(int i = index; i<= end; i++){
if(inorder[i] == k){
return i;
}
}
return -1;
}
}
106. 从中序与后序遍历序列构造二叉树 - 力扣(Leetcode)
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length == 1)
return new TreeNode(inorder[0]);
return buildTreeChild(inorder, postorder, 0, inorder.length-1, postorder.length-1);
}
int i = 0;
public TreeNode buildTreeChild(int[] inorder, int[] postorder, int form, int end, int len){
if(form > end) return null;
if(i > len) return null;
TreeNode tmp = new TreeNode(postorder[len-i]);
int index = findTree(inorder, postorder[len-i],form,end);
i++;
tmp.right = buildTreeChild(inorder, postorder, index+1, end, len);
tmp.left = buildTreeChild(inorder, postorder, form, index-1, len);
return tmp;
}
public int findTree(int[] inorder, int key, int form, int end){
for(int i = form; i <= end; i++){
if(inorder[i] == key)
return i;
}
return -1;
}
}
关于二叉树的知识点还有很多,例如红黑树、AVL树……
我们下期再见!
这篇博客如果对你有帮助,给博主一个免费的点赞以示鼓励,欢迎各位🔎点赞👍评论收藏⭐,谢谢!!!