深圳建网站哪个好,深圳网站建设公司麦,旅游网站 源码 织梦,网上帮做一些小事赚零花钱的网站二叉树
二叉树特点是每个节点最多只能有两棵子树#xff0c;且有左右之分二叉树的数据结构如下#xff1a;
public class TreeNode {//节点的值int val;//左子树TreeNode left;//右子树TreeNode right;TreeNode(int x) { val x; }
}树节点的初始化#xff1a; int val1;T…二叉树
二叉树特点是每个节点最多只能有两棵子树且有左右之分二叉树的数据结构如下
public class TreeNode {//节点的值int val;//左子树TreeNode left;//右子树TreeNode right;TreeNode(int x) { val x; }
}树节点的初始化 int val1;TreeNode node new TreeNode(val);获取树的节点node的值 int val node.val;二叉树的节点为node求左右子树 TreeNode right node.right;TreeNode left node.left;N叉树的节点结构如下
class Node {public int val;public ListNode children;
}树的遍历
树的遍历方式有前序遍历(又叫先序遍历)、中序遍历、后序遍历 前序遍历根节点左节点右节点。 中序遍历左节点根节点右节点。 后序遍历左节点右节点根节点。
递归法
树经常会用到递归。
比如二叉树的中序遍历LeetCode94。 先序遍历、后序遍历也类似只是调换了节点的顺序而已。
public class LeetCode94 {//list设置为成员变量如果是方法内变量,无法一直添加元素private ListInteger list new ArrayList();public ListInteger inorderTraversal(TreeNode root) {if (root null) {return list;}//中序遍历左节点根节点右节点。inorderTraversal(root.left);list.add(root.val);inorderTraversal(root.right);return list;}
}比如N叉树的前序遍历LeetCode589。
class LeetCode589{//list设置为成员变量如果是方法内变量,无法一直添加元素private ListInteger list new LinkedList();public ListInteger preorder(Node root) {if(rootnull) {return list;}list.add(root.val);for (Node node : root.children) {preorder(node);}return list;}
}迭代法
树还可以用迭代法。利用栈的先进后出解题。 迭代法是DFS和BFS的基础可以多学习一下。
BFS(广度优先搜索算法)。
BFS的操作步骤如下 1、使用 Queue的 offer()方法(或者是add()方法)把树的根节点放入 Queue 2、重复以下步骤直到 Queue为空为止(也就是while循环条件为 !queue.isEmpty()) (1)获取 Queue的size 因为Queue中存放的其实就是每一层中所有的节点, size就相当于每一层的数量也就是宽度 (2)遍历队列直到当前这一层所有的节点都遍历完(也就是while循环条件为 size-- 0 ) (3)在遍历过程中使用 Queue的 offer()方法得到队列中的节点根据节点查出它的左节点和右节点并用offer()方法放入队列中。
题目LeetCode104、LeetCode102
leetCode102二叉树的层序遍历 public ListListInteger levelOrder(TreeNode root) {ListListInteger resultList new ArrayList();if (rootnull) {return resultList;}QueueTreeNode queue new ArrayDeque();queue.add(root);//遍历队列while (!queue.isEmpty()) {//此处有坑一定要先把每一层的数量记录下来不然队列的长度发生变化遍历次数不一样int nqueue.size();//层序遍历从最上层到最下层可以用BFS把每一层的节点放到list里面。//每一层都有一个listListInteger list new ArrayList();for (int i0;in;i) {//用poll拿出队列的节点TreeNode node queue.poll();list.add(node.val);//把当前节点的左子节点、右子节点放入到队列中。if (node.left!null) {queue.add(node.left);}if (node.right!null) {queue.add(node.right);}}resultList.add(list);}return resultList;}
}LeetCode104求二叉树的最大深度。
public class LeetCode104BFS {public int maxDepth(TreeNode root) {if (root null){return 0;}int depth 0;QueueTreeNode queue new LinkedList();//队列使用offer和poll不会抛异常//首先要将根节点放入队列中。nodes.offer(root);while (!queue.isEmpty()) {//队列中存放的其实就是每一层中所有的节点//size就相当于每一层的数量int size queue.size();//遍历一次深度就加一depth;//遍历队列中的数据直到当前这一层所有的节点都遍历完while (size-- 0) {//取出队列中的树节点TreeNode node queue.poll();//将当前节点的左右子树放入队列中。if (node!null node.left ! null){queue.offer(node.left);}if (node!null node.right ! null){queue.offer(node.right);}}}return depth;}
}DFS(深度优先搜索算法)
以深度优先为策略从根节点开始一直遍历到某个叶子节点。
DFS的实现方式相比于BFS应该说大同小异只是把 queue 换成了stack而已stack具有后进先出LIFO(Last Input First Output)的特性DFS的操作步骤如下 1、把起始点放入stack 2、重复下述3步骤直到stack为空为止 (1)从stack中访问栈顶的点 (2)找出与此点邻接的且尚未遍历的点(也就是子节点)进行标记然后全部放入stack中 (3)如果此点没有尚未遍历的邻接点则将此点从stack中弹出。
LeetCode589:N叉树的前序遍历。
class Solution {public ListInteger preorder(Node root) {ListInteger list new ArrayList();if (root null) return list;//将根节点数据添加到栈中StackNode stack new Stack();stack.add(root);while (!stack.empty()) {//栈顶的数据出栈root stack.pop();//在list中添加栈顶数据list.add(root.val);//将子节点全部放入栈里面由于栈是后进先出所以后面的子节点先放入for (int i root.children.size() - 1; i 0; i--)stack.add(root.children.get(i));}return list;}
}参考资料
leetCode
