海口专业网站建设,WordPress手机页面插件,自己电脑做局域网网站服务器,沈阳男科医院免费在线咨询提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣971. 翻转二叉树以匹配先序遍历二、力扣987. 二叉树的垂序遍历三、力扣666. 路径总和 IV 前言 二叉树的递归分为「遍历」和「分解问题」两种思维模式文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣971. 翻转二叉树以匹配先序遍历二、力扣987. 二叉树的垂序遍历三、力扣666. 路径总和 IV 前言 二叉树的递归分为「遍历」和「分解问题」两种思维模式这道题需要用到「遍历」的思维。
一、力扣971. 翻转二叉树以匹配先序遍历
/*** 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 {ListInteger res new ArrayList();int[] voyageArr;int i 0;boolean flag true;public ListInteger flipMatchVoyage(TreeNode root, int[] voyage) {voyageArr voyage;fun(root);if(flag false){ListInteger list new ArrayList();list.add(-1);return list;}return res;}public void fun(TreeNode root){if(root null){return;}if(root.val ! voyageArr[i]){flag false;return;}if(root.left ! null root.left.val ! voyageArr[i]){res.add(root.val);TreeNode temp root.left;root.left root.right;root.right temp;}fun(root.left);fun(root.right);}
}二、力扣987. 二叉树的垂序遍历
/*** 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 {class Triple{TreeNode node;int row, col;public Triple(TreeNode node, int row, int col){this.node node;this.row row;this.col col;}}LinkedListListInteger res new LinkedList();ListTriple nodes new ArrayList();public ListListInteger verticalTraversal(TreeNode root) {traverse(root,0,0);Collections.sort(nodes, (tri1,tri2)-{if(tri1.col ! tri2.col){return tri1.col - tri2.col;}else if(tri1.row ! tri2.row){return tri1.row - tri2.row;}else{return tri1.node.val - tri2.node.val;}});int pre Integer.MIN_VALUE;for(int i 0; i nodes.size(); i ){Triple cur nodes.get(i);if(cur.col ! pre){res.addLast(new LinkedListInteger());pre cur.col;}res.getLast().add(cur.node.val);}return res;}public void traverse(TreeNode root, int row, int col){if(root null){return ;}nodes.add(new Triple(root,row,col));traverse(root.left, row1, col-1);traverse(root.right, row1, col 1);}
}三、力扣666. 路径总和 IV
class Solution {MapInteger,Integer tree new HashMap();int sum 0;public int pathSum(int[] nums) {for(int i 0; i nums.length; i ){int value nums[i]%10;int code nums[i]/10;tree.put(code,value);}int rootCode nums[0]/10;fun(rootCode,0);return sum;}public void fun(int code, int path){if(!tree.containsKey(code)){return;}int value tree.get(code);int[] pos decode(code);int depth pos[0], id pos[1];int leftCode encode(depth1, 2*id-1);int rightCode encode(depth1,2*id);if(!tree.containsKey(leftCode) !tree.containsKey(rightCode)){sum path value;return;}fun(leftCode, path value);fun(rightCode, path value);}public int[] decode(int code){int id code%10;int depth code/10;return new int[]{depth,id};}public int encode(int depth, int id){return depth*10 id;}
}
