dede手机网站建设教程,布吉做棋牌网站建设哪家公司便宜,中国公路建设行业协会网站这么上不,wordpress paginate_links文章目录 层序遍历——队列实现分析Java完整代码 先序遍历——中左右分析递归实现非递归实现——栈实现 中序遍历——左中右递归实现非递归实现——栈实现 后续遍历——左右中递归实现非递归实现——栈加标志指针实现 总结 层序遍历——队列实现
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点
分析
借助队列存储的方式实现。队列这个数据结构是先入先出的。
具体步骤 1、将根节点入队 2、出队首节点将队首节点的左右非空孩子入队 3、重复2操作直到队列为空
注意Java的队列由linkedList实现的这个需要注意一下。
Java完整代码
/*** 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 res new ArrayList(); if (root null) {return res;}LinkedListTreeNode queue new LinkedList(); // Java的队列由linkedList实现的queue.add(root);while (!queue.isEmpty()) {ListInteger list new ArrayList();int current_queue_size queue.size();for (int i 0; i current_queue_size; i) {TreeNode top queue.getFirst();list.add(top.val);if (top.left ! null) {queue.add(top.left);}if (top.right ! null) {queue.add(top.right);}queue.removeFirst();}res.add(list);}return res;}}先序遍历——中左右
给你二叉树的根节点 root 返回它节点值的 前序 遍历。
分析
前序遍历是先访问根节点再左孩子然后右孩子。
递归实现
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();preorder(root, res);return res;}public void preorder(TreeNode root, ListInteger res) {if (root null) {return;}res.add(root.val);preorder(root.left, res);preorder(root.right, res);}
}非递归实现——栈实现
借助栈数据结构 * 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 preorderTraversal(TreeNode root) {ListInteger result new ArrayList();if (root null) {return result;}StackTreeNode stack new Stack();TreeNode p root;TreeNode tmp;while (p ! null || !stack.isEmpty()) {// 一路向左if (p ! null) {result.add(p.val);stack.push(p);p p.left;} else {tmp stack.pop();p tmp.right;}}return result;}
}中序遍历——左中右
递归实现
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();inorder(root, res);return res;}public void inorder(TreeNode root, ListInteger res) {if (root null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
}非递归实现——栈实现
/*** 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 result new ArrayList();if (root null) {return result;}StackTreeNode stack new Stack();TreeNode p root;TreeNode tmp;while (p ! null || !stack.isEmpty()) {// 一路向左if (p ! null) {stack.push(p);p p.left;} else {tmp stack.pop();result.add(tmp.val);p tmp.right;}}return result;}
}后续遍历——左右中
递归实现
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();postorder(root, res);return res;}public void postorder(TreeNode root, ListInteger res) {if (root null) {return;}postorder(root.left, res);postorder(root.right, res);res.add(root.val);}
}非递归实现——栈加标志指针实现
/*** 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 result new ArrayList();if (root null) {return result;}StackTreeNode stack new Stack();TreeNode p root;TreeNode tmp;TreeNode review null;while (p ! null || !stack.isEmpty()) {// 一路向左if (p ! null) {stack.push(p);p p.left;} else {tmp stack.peek();if (tmp.right null || review tmp.right) {result.add(tmp.val);review stack.pop();} else {p tmp.right;}}}return result;}
}总结
对于树的问题更多能通过递归去简化问题更好解决实际问题。
ps:计划每日更新一篇博客今日2023-04-29日更第十三天。 昨日更新 反转字符串
