wordpress网站定时更新没有发布,前端是什么工作,微博优惠券网站怎么做,手工制作过程层序遍历
思路#xff1a; 需要借用一个辅助数据结构即队列来实现#xff0c;队列先进先出#xff0c;符合一层一层遍历的逻辑#xff0c;而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。 而这种层序遍历方式就是图论中的广度优先遍历#xff0c;只不过我们应用在…层序遍历
思路 需要借用一个辅助数据结构即队列来实现队列先进先出符合一层一层遍历的逻辑而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。 而这种层序遍历方式就是图论中的广度优先遍历只不过我们应用在二叉树上。 使用队列实现二叉树广度优先遍历动画如下 注意 不要忽略root为空的情况否则会报错。
/*** 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) {DequeTreeNode queuenew LinkedList();ListListInteger resnew ArrayList();if(rootnull) return res;queue.add(root);while(!queue.isEmpty()){int lenqueue.size();ListInteger tempnew ArrayList();for(int i0;ilen;i){TreeNode curqueue.poll();temp.add(cur.val);if(cur.left!null) queue.add(cur.left);if(cur.right!null) queue.add(cur.right);}res.add(temp);}return res;}
}226.翻转二叉树
可以发现想要翻转它其实就把每一个节点的左右孩子交换一下就可以了。
关键在于遍历顺序前中后序应该选哪一种遍历顺序 一些同学这道题都过了但是不知道自己用的是什么顺序
这道题目使用前序遍历和后序遍历都可以唯独中序遍历不方便因为中序遍历会把某些节点的左右孩子翻转了两次建议拿纸画一画就理解了。 以递归的前序遍历为例
/*** 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) {DequeTreeNode queuenew LinkedList();ListListInteger resnew ArrayList();if(rootnull) return res;queue.add(root);while(!queue.isEmpty()){int lenqueue.size();ListInteger tempnew ArrayList();for(int i0;ilen;i){TreeNode curqueue.poll();temp.add(cur.val);if(cur.left!null) queue.add(cur.left);if(cur.right!null) queue.add(cur.right);}res.add(temp);}return res;}
}101.对称二叉树
思路 首先想清楚判断对称二叉树要比较的是哪两个节点要比较的可不是左右节点
对于二叉树是否对称要比较的是根节点的左子树与右子树是不是相互翻转的理解这一点就知道了其实我们要比较的是两个树这两个树是根节点的左右子树所以在递归遍历的过程中也是要同时遍历两棵树。
1. 确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的进而判断这个树是不是对称树所以要比较的是两个树参数自然也是左子树节点和右子树节点。
返回值自然是bool类型。
代码如下
public boolean compare(TreeNode left,TreeNode right)2.确定终止条件
要比较两个节点数值相不相同首先要把两个节点为空的情况弄清楚否则后面比较数值的时候就会操作空指针了。
节点为空的情况有注意我们比较的其实不是左孩子和右孩子所以如下我称之为左节点右节点
左节点为空右节点不为空不对称return false 左不为空右为空不对称 return false 左右都为空对称返回true 此时已经排除掉了节点为空的情况那么剩下的就是左右节点不为空
左右都不为空比较节点数值不相同就return false 此时左右节点不为空且数值也不相同的情况我们也处理了。
代码如下
if(leftnull rightnull) return true;//两个都为空else if(leftnullright!null || left!nullrightnull) return false;//其中一个为空else if(left.val!right.val) return false;//都不为空注意上面最后一种情况我没有使用else而是else if 因为我们把以上情况都排除之后剩下的就是 左右节点都不为空且数值相同的情况。
3. 确定单层递归的逻辑
此时才进入单层递归的逻辑单层递归的逻辑就是处理 左右节点都不为空且数值相同的情况。
比较二叉树外侧是否对称传入的是左节点的左孩子右节点的右孩子。 比较内侧是否对称传入左节点的右孩子右节点的左孩子。 如果左右都对称就返回true 有一侧不对称就返回false 。 代码如下
boolean incompare(left.right,right.left);boolean outcompare(left.left,right.right);return inout;如上代码中我们可以看出使用的遍历方式左子树左右中右子树右左中所以我把这个遍历顺序也称之为“后序遍历”尽管不是严格的后序遍历。
/*** 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(rootnull) return true;else return compare(root.left,root.right);}public boolean compare(TreeNode left,TreeNode right){//充分考虑空节点的情况防止出现空指针异常if(leftnull rightnull) return true;else if(leftnullright!null || left!nullrightnull) return false;else if(left.val!right.val) return false;else{boolean incompare(left.right,right.left);boolean outcompare(left.left,right.right);return inout;}}
}
