二叉树系列(遍历/dfs/bfs)10.10

一、二叉树的右视图(遍历)

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

（如果右子树为空的话，那么右视图中看到的就是左子树的节点）

bfs层序遍历:

思路：

需要用到一个队列，然后把每一层中的节点添加到队列中，遍历到最后一个节点的时候就是最右边的，添加到res中即可。

代码：

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> res=new ArrayList<>();Queue<TreeNode> queue=new ArrayDeque<>();if(root==null)return res;queue.add(root);while(!queue.isEmpty()){int size=queue.size();for(int i=0;i<size;i++){TreeNode cur=queue.poll();if(cur.left!=null)queue.add(cur.left);if(cur.right!=null)queue.add(cur.right);if(i==size-1)res.add(cur.val); }}return res;}
}

dfs右序遍历

思路：

因为题目中要求我们返回右视图的结果集。因此我们首先递归右子树，然后再去递归左子树。

如果右子节点一直存在的话，那么就一直往下dfs搜索，添加到res中；

如果右子节点为null的话，那么就向上返回，往左递归。注意这里要判断当前的深度和res的大小。只有depth==res.size()时，说明该层该元素是第一个访问的。

代码：

class Solution {List<Integer> res=new ArrayList<>();public List<Integer> rightSideView(TreeNode root) {dfs(root,0);return res;}public void dfs(TreeNode root,int depth){if(root==null)return;if(res.size()==depth){res.add(root.val);//每一层只能添加一个子节点}depth++;dfs(root.right,depth);dfs(root.left,depth);}
}

二、路经总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

思路：

1.首先题目要求我们的是从根节点到叶子节点,所以我们写终止条件的时候一定要写叶子结点的终止条件，如下：

if(root==null)return false;
if(root.left==null&&root.right==null)return targetSum==root.val;

我第一次写成了

if(root==null)return targetSum==0;

 这样就会导致和题意不符合，就不是根节点到叶子节点了。

2.然后，就向左右子节点遍历即可，但是要注意的是，要先判断左右子节点是否为空。

        boolean left=false;boolean right=false;if(root.left!=null)left=dfs(root.left,targetSum-root.val);if(root.right!=null)right=dfs(root.right,targetSum-root.val);

代码： 

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root==null)return false;return dfs(root,targetSum);}public boolean dfs(TreeNode root,int targetSum){if(root==null)return false;if(root.left==null&&root.right==null)return targetSum==root.val;boolean left=false;boolean right=false;if(root.left!=null)left=dfs(root.left,targetSum-root.val);if(root.right!=null)right=dfs(root.right,targetSum-root.val);return left||right;}
}

三、二叉树最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。

dfs深搜：

思路:

我们要找到根节点到叶子节点中的最短路径。那我们就要去判断每次遍历的节点。

如果是叶子节点，返回1；

如果是null，返回0；

如果左右节点有一个为空，那么就返回非空那边的深度；

如果两个都不为空，那么就返回其中的较小值。

代码:

class Solution {public int minDepth(TreeNode root) {if(root==null)return 0;int leftDepth=minDepth(root.left);int rightDepth=minDepth(root.right);//如果一边为空 或者都不为空if(root.left==null||root.right==null)return leftDepth+rightDepth+1;//如果两边都为空 就是一个叶子节点return Math.min(leftDepth,rightDepth)+1;}
}

bfs广搜:

思路：

层序遍历的思路

代码：

class Solution {public int minDepth(TreeNode root) {if(root==null)return 0;int res=0;Queue<TreeNode> queue=new ArrayDeque<>();queue.add(root);while(!queue.isEmpty()){int size=queue.size();res++;for(int i=0;i<size;i++){TreeNode cur=queue.poll();if(cur.left==null&&cur.right==null)return res;if(cur.left!=null)queue.add(cur.left);if(cur.right!=null)queue.add(cur.right);}}return res;}
}

四、求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。叶节点 是指没有子节点的节点。

思路：

如果遍历到第x个节点，我们需要把值求出来，然后传给下一个节点，下一个节点*10+root.val之后，再传给下一个节点。当遇到节点为叶子结点的时候，就返回值。

代码：

public int dfs(TreeNode node,int cur){if(node==null)return 0;int newCur=cur*10+node.val;if(node.left==null&&node.right==null)return newCur;int leftNum=dfs(node.left,newCur);int rightNum=dfs(node.right,newCur);return leftNum+rightNum;}