leetcode-13-[110]平衡二叉树[257]二叉树的所有路径[404]左叶子之和[222]完全二叉树的节点个数

本文主要是介绍leetcode-13-[110]平衡二叉树[257]二叉树的所有路径[404]左叶子之和[222]完全二叉树的节点个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、[110]平衡二叉树

注意：注释的1、2两处得有返回值-1

class Solution {public boolean isBalanced(TreeNode root) {int result = getHeight(root);return result != (-1);}//高度public int getHeight(TreeNode node){if(node==null){return 0;}int lh = getHeight(node.left);//注意1if(lh==-1){return -1;}int rh = getHeight(node.right);//注意2if(rh==-1){return -1;}if(Math.abs(lh-rh)>1){return -1;}return Math.max(lh,rh)+1;}
}

二、[257]二叉树的所有路径

class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> res=new ArrayList<>();List<Integer> path=new ArrayList<>();treePaths(root,res,path);return res;}void treePaths(TreeNode node,List<String> res,List<Integer> path){path.add(node.val);if(node.left==null&&node.right==null){String tmp="";for(int i=0;i< path.size()-1;i++){tmp+=path.get(i);tmp+="->";}tmp+=path.get(path.size()-1);res.add(tmp);}//注意不为空的判断if(node.left!=null) {treePaths(node.left, res, path);path.remove(path.size() - 1);}if(node.right!=null) {treePaths(node.right, res, path);path.remove(path.size() - 1);}}}

三、[404]左叶子之和

重点：注意不能直接返回 root.left.val，即它的if条件 不是 终止递归的条件

如：根节点的左子树，只有一个节点，符合条件，此时直接返回

而右子树还没有进行递归，解答错误。

应该暂存tmp=root.left.val，

在左右子树均进入递归后，再返回。

另：后序遍历 逻辑更加容易理解。

class Solution {public int sumOfLeftLeaves(TreeNode root) {if(root==null){return 0;}if(root.left==null&&root.right==null){return 0;}//防止出现根节点的左节点满足条件，就直接返回了，递归还没有进行//前序遍历//还有右子树没有遍历，不能直接returnint tmp=0;if(root.left!=null&&root.left.left==null&&root.left.right==null){tmp=root.left.val;}int lv = sumOfLeftLeaves(root.left);int rv = sumOfLeftLeaves(root.right);return lv+rv+tmp;//0+0+tmp//后序遍历
//        int lv = sumOfLeftLeaves(root.left);
//        int rv = sumOfLeftLeaves(root.right);
//        int tmp=0;
//        if(root.left!=null&&root.left.left==null&&root.left.right==null)
//        {
//              tmp=root.left.val;
//        }
//        return tmp+lv+rv;}
}

四、[222]完全二叉树的节点个数

class Solution {public int countNodes(TreeNode root) {if(root==null){return 0;}int ln = countNodes(root.left);int rn = countNodes(root.right);return ln+rn+1;}
}

这篇关于leetcode-13-[110]平衡二叉树[257]二叉树的所有路径[404]左叶子之和[222]完全二叉树的节点个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---