网站制作金华公司电话,无锡加盟网站建设,搭建小网站,建设网站学什么时候开始《代码随想录》--二叉树 第一部分 1、二叉树的递归遍历2、二叉树的迭代遍历3、统一风格的迭代遍历代码4、二叉树的层序遍历226.翻转二叉树 1、二叉树的递归遍历
前序遍历
中序遍历
后序遍历 代码 前序遍历
class Solution {public ListInteger preorderTraversal(T… 《代码随想录》--二叉树 第一部分 1、二叉树的递归遍历2、二叉树的迭代遍历3、统一风格的迭代遍历代码4、二叉树的层序遍历226.翻转二叉树 1、二叉树的递归遍历
前序遍历
中序遍历
后序遍历 代码 前序遍历
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger list new ArrayList();preOrder(root,list);return list;}public void preOrder(TreeNode root,ListInteger list){if(root null) return;list.add(root.val);preOrder(root.left,list);preOrder(root.right,list);}
}中序遍历
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger list new ArrayList();inOrder(root,list);return list;}public void inOrder(TreeNode root,ListInteger list){if(root null) return;inOrder(root.left,list);list.add(root.val);inOrder(root.right,list);}
}后序遍历
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger list new ArrayList();postOrder(root,list);return list;}public void postOrder(TreeNode root,ListInteger list){if(root null) return;postOrder(root.left,list);postOrder(root.right,list);list.add(root.val);}
}2、二叉树的迭代遍历
前序遍历
中序遍历
后序遍历 代码 前序遍历
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();if(root null) return result;StackTreeNode stack new Stack();stack.push(root);while(!stack.isEmpty()){TreeNode node stack.pop();result.add(node.val);if(node.right ! null) stack.push(node.right);if(node.left ! null) stack.push(node.left);}return result;}
}中序遍历
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger list new ArrayList();StackTreeNode stack new Stack();TreeNode cur root;while(cur ! null || !stack.isEmpty()){if(cur ! null){stack.push(cur);cur cur.left;}else{TreeNode node stack.pop();list.add(node.val);cur node.right;}}return list;}
}后序遍历
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger list new ArrayList();if(root null) return list;StackTreeNode stack new Stack();stack.push(root);while(!stack.isEmpty()){TreeNode node stack.pop();list.add(node.val);if(node.left ! null) stack.push(node.left);if(node.right ! null) stack.push(node.right);}Collections.reverse(list);return list;}
}分析 非递归的遍历都需要借助栈来编写代码前序遍历 前序遍历是中左右的顺序先把中间节点放入栈中再放入右孩子(为什么因为栈先入后出)再放入左孩子 中序遍历 中序遍历的顺序是左中右但是我们的处理顺序和访问顺序不一致所以借助指针定义一个cur指针帮助我们遍历栈用来处理节点上的元素 后序遍历 后序遍历的顺序是左右中可以根据前序遍历改变得到将遍历顺序改为中左右最后得到的结果是中右左反转数组得到正确结果
3、统一风格的迭代遍历代码
前面的迭代遍历代码风格不统一不像递归代码一样修改代码的位置就能写出三种遍历方式这里借助空节点标记法 代码 前序
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger list new ArrayList();StackTreeNode stack new Stack();if(root ! null) stack.push(root);while(!stack.isEmpty()){TreeNode node stack.peek();if(node ! null){node stack.pop();if(node.right ! null) stack.push(node.right);if(node.left ! null) stack.push(node.left);stack.push(node);stack.push(null);}else{stack.pop();node stack.pop();list.add(node.val);}}return list;}
}中序
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger list new ArrayList();StackTreeNode stack new Stack();if(root ! null) stack.push(root);while(!stack.isEmpty()){TreeNode node stack.peek();if(node ! null){node stack.pop(); //将该节点弹出if(node.right ! null) stack.push(node.right); //添加左节点stack.push(node); //添加中节点stack.push(null); //中间节点访问过但是还没有处理加入空节点标记if(node.left ! null) stack.push(node.left); //添加右节点}else{stack.pop(); //弹出空节点node stack.pop(); //取出栈中元素list.add(node.val);}}return list;}
}后序
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger list new ArrayList();StackTreeNode stack new Stack();if(root ! null) stack.push(root);while(!stack.isEmpty()){TreeNode node stack.peek();if(node ! null){node stack.pop();stack.push(node);stack.push(null);if(node.right ! null) stack.push(node.right);if(node.left ! null) stack.push(node.left);}else{stack.pop();node stack.pop();list.add(node.val);}}return list;}
}分析 可以看到使用空节点标记法只需要修改两行代码就能写出不同的遍历代码
4、二叉树的层序遍历
学会二叉树的层序遍历可以一口气打完以下十题
102.二叉树的层序遍历107.二叉树的层次遍历II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II104.二叉树的最大深度111.二叉树的最小深度 代码 102题 迭代
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()){ListInteger tempList new ArrayList();int len queue.size();while(len 0){TreeNode node queue.poll();tempList.add(node.val);if(node.left ! null) queue.offer(node.left);if(node.right ! null) queue.offer(node.right);len--;}list.add(tempList);}return list;}
}递归
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger list new ArrayList();level(root,list,0);return list;}public void level(TreeNode node,ListListInteger list,int depth){if(node null) return;depth;if(list.size() depth){ListInteger tempList new ArrayList();list.add(tempList);}list.get(depth-1).add(node.val);level(node.left,list,depth);level(node.right,list,depth);}
}分析 迭代法借助了数据结构队列先入先出。
226.翻转二叉树
leetcode链接 代码 前序遍历
class Solution {public TreeNode invertTree(TreeNode root) {preOrderReverse(root);return root;}public void preOrderReverse(TreeNode node){if(node null) return;TreeNode temp node.left;node.left node.right;node.right temp;preOrderReverse(node.left);preOrderReverse(node.right);}
}后序遍历
class Solution {public TreeNode invertTree(TreeNode root) {preOrderReverse(root);return root;}public void preOrderReverse(TreeNode node){if(node null) return;preOrderReverse(node.left);preOrderReverse(node.right);TreeNode temp node.left;node.left node.right;node.right temp;}
}BFS
class Solution {public TreeNode invertTree(TreeNode root) {if(root null) return root;QueueTreeNode queue new LinkedList();queue.offer(root);while(queue.size()0){int size queue.size();for(int i 0;i size;i){TreeNode node queue.poll();TreeNode temp node.left;node.left node.right;node.right temp;if(node.left ! null) queue.offer(node.left);if(node.right ! null) queue.offer(node.right);}}return root;}
}统一法
class Solution {public TreeNode invertTree(TreeNode root) {if(root null) return root;StackTreeNode stack new Stack();stack.push(root);while(!stack.isEmpty()){TreeNode node stack.peek();if(node ! null){stack.pop();if(node.right ! null) stack.push(node.right);if(node.left ! null) stack.push(node.left);stack.push(node);stack.push(null);}else{stack.pop();node stack.pop();TreeNode temp node.left;node.left node.right;node.right temp;}}return root;}
}分析 第一种递归的方式只能写前序和后序中序代码会导致有些节点反转了两次第二种BFS也就是层序遍历第三种统一的写法满足前中后序三种遍历方式
