【改造先序遍历】222. 完全二叉树的节点个数

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);}
}