商城网站怎么建,wordpress 默认登录,适合个人做的网站有哪些东西吗,南宁网站seo外包222. 完全二叉树的节点个数
解题思路-先序
直接改造先序遍历算法针对一个节点 如果节点为空 那么直接返回0其余交给递归 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* …222. 完全二叉树的节点个数
解题思路-先序
直接改造先序遍历算法针对一个节点 如果节点为空 那么直接返回0其余交给递归 /*** 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 {public int countNodes(TreeNode root) {// 直接改造先序遍历算法// 针对一个节点做那些事情if(root null){return 0;}return 1 countNodes(root.left) countNodes(root.right);}
}
解题思路-降低时间复杂度
对于一颗完全二叉树 它的子树 一定有满二叉树
/*** 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 {public int countNodes(TreeNode root) {TreeNode l root,r root;// 记录左右子树的高度int hl 0;int hr 0;while(l ! null){l l.left;hl;}while(r ! null){r r.right;hr;}// 如果左右子树高度相等 那么说明是一颗满二叉树 完全二叉树一定有子树是满二叉树// 该条件一定会出发if(hl hr){return (int) Math.pow(2,hl) - 1;}// 如果左右二叉树的高度不一样 直接按照普通的二叉树进行计算 return 1 countNodes(root.left) countNodes(root.right);}
}
