因为我二叉树建树很烂,建了半天树,特此记录
题目
1457. 二叉树中的伪回文路径

分析
问题很简单,只需要建树,然后维护一个哈希表,dfs的时候记录下每个数字出现的次数,到了叶子节点后(没有左右孩子),遍历该哈希表,如果出现了两次奇数个数字,则说明不能构成回文
如上图例1,深度优先最左边的枝,数字序列为 2 3 3
,那么哈希表为 1 2
。即2出现了一次,3出现了两次,则可以构成回文 3 2 3
对于 2 3 1
这个遍历,由于哈希表为 1 1 1
,即奇数个数字出现了两次以上,则不能构成回文
复盘
关键在于建树不熟练,导致时间慢了
序列为层序遍历的数组
对于第 i
个元素,应该判断他是否有孩子节点,如果有,则给孩子节点创建一个树,使用递归建树
层序遍历的数组,他的左孩子索引为 i * 2 + 1
, 右孩子索引为 (i + 1) * 2
对于左孩子,应有
if (now * 2 + 1 <= n - 1){ int left = now * 2 + 1; TreeNode childLeft = initTree(new TreeNode(), nums, left * 2 + 1); TreeNode childRight = initTree(new TreeNode(), nums, (left + 1) * 2)); tree.left = new TreeNode(nums[now * 2 + 1], childLeft, childRight; }
|
这里的 left * 2 + 1
是对于 i
左孩子的左孩子的当前索引
同理可得右孩子递归写法
if ((now + 1) * 2 <= n - 1){ int right = (now + 1) * 2; TreeNode childLeft = initTree(new TreeNode(), nums, right * 2 + 1); TreeNode childRight = initTree(new TreeNode(), nums, (right + 1) * 2)); tree.right = new TreeNode(nums[now * 2 + 1], childLeft, childRight; }
|
完整代码实现
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 int pseudoPalindromicPaths (TreeNode root) { dfs(root); return this.ans; } int ans = 0; int[] hashmap = new int[10]; public TreeNode initTree(TreeNode tree, int[] nums, int now){ int n = nums.length; if (now >= n || nums[now] == -1) return null; tree.val = nums[now]; if (now * 2 + 1 <= n - 1 && nums[now * 2 + 1] != -1){ tree.left = new TreeNode(nums[now * 2 + 1], initTree(new TreeNode(), nums, (now * 2 + 1) * 2 + 1), initTree(new TreeNode(), nums, (now + 2) * 2)); } if ((now + 1) * 2 <= n - 1 && nums[(now + 1) * 2] != -1){ tree.right = new TreeNode(nums[(now + 1) * 2], initTree(new TreeNode(), nums, (now + 1) * 2 * 2 + 1), initTree(new TreeNode(), nums, ((now + 1) * 2 + 1) * 2)); } return tree; }
public void dfs(TreeNode tree){ if(tree == null){ return; } hashmap[tree.val]++; dfs(tree.left); dfs(tree.right); if(tree.left == null && tree.right == null){ boolean flag = false, flag1 = false; for(int i:hashmap){ if(flag && i % 2 != 0){ flag1 = true; break; } if(i % 2 != 0){ flag = true; } } if(!flag1) ans++; } hashmap[tree.val]--; } } public class LC1457 {
public static void main(String[] args) { Solution mysolution = new Solution(); int[] nums = new int[]{2,3,1,3,1,-1,1}; TreeNode tree = mysolution.initTree(new TreeNode(), nums, 0); System.out.println(mysolution.pseudoPalindromicPaths(tree)); } }
|