赞
踩
给你一个整数 n ,请你找出所有可能含 n 个节点的 真二叉树 ,并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。
答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。
真二叉树 是一类二叉树,树中每个节点恰好有 0 或 2 个子节点。
输入:n = 7
输出:[[0,0,0,null,null,0,0,null,null,0,0],
[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],
[0,0,0,0,0,null,null,null,null,0,0],
[0,0,0,0,0,null,null,0,0]]
【思路】:
本题很有难度。做了我一个多小时。
但是思路其实不算很难,偶数时肯定没有,主要是奇数情况。
比如dp[7]的所有情况都是建立在dp[5]的基础上的。因为在所有n=5的子树下面找叶子节点挂两个节点,就变成n=7的一个解了。
因此我们找到了大问题依赖于小问题。即 dp[k]依赖于dp[k - 2]
本题注意几个点:
1、结果一定要去重。所谓重复指的是,结构相同的树。
2、如何实现对一棵树的浅拷贝。copy
【代码】:
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ //给一个根节点,复制一棵树。实现浅拷贝 var copy = function(node){ if(node == null) return null; var newRoot = new TreeNode(node.val); newRoot.left = copy(node.left); newRoot.right = copy(node.right); return newRoot; } //判断两个树结构是否相同。return boolean var isStructSame = function(node1, node2){ if(node1 == null && node2 == null) return true; if(node1 == null) return false; if(node2 == null) return false; if(node1.val != node2.val) return false; return isStructSame(node1.left, node2.left) && isStructSame(node1.right, node2.right); } var order = function(node, res, root,ii){ if(node){ //如果是叶子节点 if(node.left == null && node.right == null){ node.left = new TreeNode(0); node.right = new TreeNode(0); let newNode = copy(root); res.push(newNode); node.left = null; node.right = null; } order(node.left, res, root,ii); order(node.right, res, root,ii); } } var appendTwoNodeOnLeaves = function(node,i){ var res = []; order(node, res, node,i); return res; } /** * @param {number} n * @return {TreeNode[]} */ var allPossibleFBT = function(n) { var dp = new Array(n + 1); var node = new TreeNode(0);node.left = null;node.right = null; dp[1] = [node]; for(let i = 2;i <= n;i++){ if(i % 2 == 0){ dp[i] = []; }else{ dp[i] = []; let arr = dp[i - 2]; //TreeNode[] for(let j = 0;j < arr.length;j++){ //取出一个树的根节点 let root = arr[j]; //在叶子节点上加两个节点的所有情况 let result = appendTwoNodeOnLeaves(root,i); //把每个可能的树加入dp[i] //下面所做的就是为了去重 for(let k =0 ;k < result.length;k++){ let hasSame = false; for(let h = 0;h < dp[i].length;h++){ if(isStructSame(result[k], dp[i][h])){ hasSame = true; break; } } //如果结果集中没有,就加入。实现去重 if(!hasSame){ dp[i].push(result[k]); } } } } } return dp[n] };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。