算法学习笔记（五）：二叉树一遍历、DFS

一.遍历二叉树

二叉树TreeNode类

/*** 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;*     }* }*/

前：NLR

中：LNR

后：LRN

二叉树遍历的本质是递归。

1.二叉树的前序遍历

        给你二叉树的根节点 root，返回它节点值的 前序 遍历

class Solution {public List<Integer> preorderTraversal(TreeNode root) {//前序遍历就是NLR 先输出根节点 再输出左节点 再输出右节点//然后以此类推，每个节点都是这样的顺序 所以这是一个子问题//而整个二叉树可以由多个子问题解决 所以可以递归List<Integer> list = new ArrayList<>();dfs(root, list);return list;}private void dfs(TreeNode root, List<Integer> list) {if (root == null) return;list.add(root.val);dfs(root.left, list);dfs(root.right, list);}    
}

2.二叉树的中序遍历

        给定一个二叉树的根节点 root，返回它的中序遍历

class Solution {public List<Integer> inorderTraversal(TreeNode root) {//中序遍历 LNRList<Integer> list = new ArrayList<>();dfs(root, list);return list;}private void dfs(TreeNode root, List<Integer> list) {if (root == null) return;dfs(root.left, list);list.add(root.val);dfs(root.right, list);}
}

3.二叉树的后续遍历

        给你一棵二叉树的根节点 root，返回它的 后续遍历

class Solution {public List<Integer> postorderTraversal(TreeNode root) {//后续遍历就是LRNList<Integer> list = new ArrayList<>();dfs(root, list);return list;}public void dfs(TreeNode root, List<Integer> list) {if (root == null) return;dfs(root.left, list);dfs(root.right, list);list.add(root.val);}
}

4.叶子相似的树

        请考虑一棵二叉树上所有的叶子，这些叶子的值按照从左到右的顺序排列形成一个 叶值序列

        举个例子，如图所示，给定一棵叶值序列为 [6, 7, 4, 9, 8] 的树

        如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的

        如果两棵树是叶相似，返回true，否则返回false

class Solution {public boolean leafSimilar(TreeNode root1, TreeNode root2) {/**按照题目，叶值是从左到右排列的所以先从左子树开始遍历，找到叶子节点保存下来*/StringBuilder sb1 = new StringBuilder(); StringBuilder sb2 = new StringBuilder(); dfs(root1, sb1);dfs(root2, sb2);return sb1.toString().equals(sb2.toString());}private void dfs(TreeNode root, StringBuilder sb) {if (root == null) return;if (root.left == root.right) {//叶子节点 因为left right都是null//append(",")是防止比如上一个是7，下一个是14 //然后第二棵树上一个是71，下一个是4这种情况sb.append(root.val).append(",");return;}//从左到右开始遍历dfs(root.left, sb);dfs(root.right, sb);}
}

5.开幕式焰火

        [力扣挑战赛]开幕式开始了，空中绽放了一棵二叉树形的举行焰火，给定一棵二叉树 root 

        代表焰火，节点值表示巨型焰火这一位置的颜色种类

        请帮小扣计算巨型焰火有多少种不同的颜色。

        示例：

        输入：root = [1, 3, 2, 1, null, 2]

        输出：3 ，有3种颜色，分别是颜色1，2，3

class Solution {public int numColor(TreeNode root) {/**这个就是纯遍历二叉树，然后判断每个节点的不同的值有多少个*/Set<Integer> set = new HashSet<>();dfs(root, set);return set.size();}private void dfs(TreeNode root, Set<Integer> set) {if (root == null) return;set.add(root.val);dfs(root.left, set);dfs(root.right, set);}
}

6.左叶子之和

        给定二叉树的根节点 root，返回所有的左叶子之和

class Solution {public int sumOfLeftLeaves(TreeNode root) {//叶子节点就是没有左右子节点的节点//重点是如何判断是左叶子return dfs(root);}private int dfs(TreeNode root) {if (root == null) return 0;int sum = 0;//如果当前节点有左节点并且左节点是叶子节点if (root.left != null && isLeaf(root.left)) {//直接计算左叶子节点之和sum += root.left.val;}//继续递归计算左子树和右子树的左叶子节点之和sum += dfs(root.left);sum += dfs(root.right);return sum;}private boolean isLeaf(TreeNode root) {return root.left == root.right;}
}

  二.自顶向下DFS

在 递 的过程中维护值

1.二叉树的最大深度

        给定一个二叉树 root，返回其最大深度

        二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数

        示例：

              

class Solution {public int maxDepth(TreeNode root) {//二叉树的最大深度公式：//max = Math.max(左子树深度，右子树深度) + 1//所以就是遍历左右子树的深度 然后+1(根节点)就是二叉树的最大深度//然后同理，每个节点的最大深度都是等于它的左右子数最大深度+1//这样就可以递归解决这个问题 每个节点的算法都是一致的if (root == null) return 0;int left = maxDepth(root.left);int right = maxDepth(root.right);return Math.max(left, right) + 1;}
}

2.二叉树的最小深度

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

        最小深度是从根节点到最近叶子节点的最短路径上的节点数量

class Solution {private int min = Integer.MAX_VALUE;    //不考虑多线程问题public int minDepth(TreeNode root) {//最小深度 也就是说到达最短叶子节点的节点数//想一下 怎么做？//上来直接判断当前节点是否是叶子节点 是的话就直接返回//这样是不是就是最小的？//但是没办法判断跟其他的比呀//增加一个全局变量 用来记录是叶子节点的时候节点数 每次只要最小的//传入一个count，用来记录当前叶子节点到根节点这条路径的节点数dfs(root, 0);return root == null ? 0 : min;}private void dfs(TreeNode root, int count) {if (root == null) return;//不是null ++ 表示节点+1count++;//如果当前节点是叶子节点 那么就算是到头了//计算到当前这个叶子节点的路径的总结点数和其他的作比较 if (root.left == root.right) {min = Math.min(min, count);return;}//否则继续往下递归dfs(root.left, count);dfs(root.right, count);}
}

3.路径总和

        给你二叉树的根节点 root 和一个表示目标和的整数 targetSum，判断该树中是否存在根节点

        到叶子节点的路径，这条路径上所有节点值相加等于目标 targetSum，

        存在返回true，否则返回false

        示例：

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {//还是遍历二叉树，然后每当遍历到一个叶子节点的时候，//计算一下到当前这个叶子节点的路径节点之和是否等于targetSum//然后一直递归遍历if (root == null) return false;//判断是否是叶子节点if (root.left == root.right) {return root.val == targetSum;}     //只要左右子树中有一个存在那么就是存在return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);}   
}

4.求根节点到叶子节点数字之和

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

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

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

        计算从根节点到叶节点生成的所有数字之和

class Solution {private int sum = 0;public int sumNumbers(TreeNode root) {//这题和求链表的十进制数字之和类似//所以公式是： int sum = sum * 10 + val//然后递归遍历每一个子树 然后返回sum即可//看来还是需要一个全局变量来存 不然每个//叶子节点的值没办法相加dfs(root, sum);return sum;}private void dfs(TreeNode root, int val) {if (root == null) return;int count = val * 10 + root.val;//如果当前是叶子节点就直接返回if (root.left == root.right) {sum += count;return;}//否则继续递归dfs(root.left, count);dfs(root.right, count);return;}
}

5.二叉树的右视图

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

        右侧所能看到的节点值。

        

class Solution {public List<Integer> rightSideView(TreeNode root) {/**想下这题怎么做右视图，首先肯定是先遍历右子树，如果存在右子节点，那么肯定先看到的是右节点其实就是几种情况1.当前节点的左右节点一样高 那么右视图看到的是肯定是右节点2.当前节点的右节点比左节点高，那么还是看到右节点3.当前节点的右节点比左节点低，那么右节点下面的左节点也能被看到所以总结出来，当一个子树的深度首次到达时，那么这个节点就在右视图中但是得要先递归遍历右子树，再递归左子树，保证右子树先到达(左右子树同样高的情况)*/List<Integer> list = new ArrayList<>();dfs(root, list, 0);return list;}private void dfs(TreeNode root, List<Integer> list, int dept) {if (root == null) return;//判断当前节点是否首次到达 如何判断//根据list size，如果list.size == dept 那么就证明首次遍历到当前深度if (list.size() == dept++) {list.add(root.val);}//然后继续按照从右到左的顺序递归dfs(root.right, list, dept);dfs(root.left, list, dept);}
}

6.统计二叉树中好节点的数目

        给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目

        好节点 定义为：从根到该节点所经过的节点中，没有任何节点的值大于该节点的值

        示例：

        

class Solution {private int count = 0;public int goodNodes(TreeNode root) {/**其实就是递归树，然后每次把遍历过的节点的最大值作为参数传到下一次递归中去，和当前节点值进行判断        */dfs(root, Integer.MIN_VALUE); return count;}private void dfs(TreeNode root, int max) {if (root == null) return;if (root.val >= max) {count++;max = root.val;}dfs(root.left, max);dfs(root.right, max);}
}