算法训练（leetcode）二刷第十三天 | 110. 平衡二叉树、*257. 二叉树的所有路径、404. 左叶子之和、*222. 完全二叉树的节点个数

110. 平衡二叉树

leetcode题目地址

借助求最大树高的思路，在求树高的过程中若发现左右子树高度相差大于1则不是平衡树。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
/*** 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 {private boolean result;public int getDepth(TreeNode root){if(root == null) return 0;int left = getDepth(root.left);int right = getDepth(root.right);if(Math.abs(left-right)>1) result = false;return left>right ? left+1 : right+1;}public boolean isBalanced(TreeNode root) {this.result = true;getDepth(root);return this.result;}
}

*257. 二叉树的所有路径

leetcode题目地址

回溯法，在访问到叶结点时开始记录路径。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
/*** 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 void backtracing(TreeNode root, List<String> result, List<Integer> path){// if(root == null) return;path.add(root.val);// 叶节点记录结果if(root.left == null && root.right == null){StringBuilder sb = new StringBuilder();for(int i=0; i<path.size()-1; i++){sb.append(path.get(i));sb.append("->");}  sb.append(path.get(path.size()-1));result.add(sb.toString());}if(root.left != null){backtracing(root.left, result, path);path.remove(path.size() - 1); // 回溯}if(root.right != null){backtracing(root.right, result, path);path.remove(path.size() - 1); // 回溯}}public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();List<Integer> path = new ArrayList<>();backtracing(root, result, path);return result;}
}

404. 左叶子之和

leetcode题目地址

思路一：递归法

递归遍历寻找左叶子返回其值，用一个标签来标记当前节点是左子树还是右子树。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
/*** 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 final static int LEFT = 0;public final static int RIGHT = 1;public int cal(TreeNode root, int tag){if(root == null) return 0;// 左叶结点if(root.left == null && root.right == null && tag == LEFT){return root.val;} // 普通节点int left = cal(root.left, LEFT);int right = cal(root.right, RIGHT);// 累加return left + right;}public int sumOfLeftLeaves(TreeNode root) {return cal(root, RIGHT);}
}

思路二：迭代法

// java
/*** 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 sumOfLeftLeaves(TreeNode root) {if(root == null) return 0;int result = 0;Stack<TreeNode> st = new Stack<>();st.push(root);while(!st.isEmpty()){TreeNode node = st.pop();if(node.left != null &&node.left.left == null &&node.left.right == null){result += node.left.val;} if(node.left != null) st.push(node.left);if(node.right != null) st.push(node.right);}return result;}
}

222. 完全二叉树的节点个数

leetcode题目地址

思路一：递归遍历计数

直接使用前序遍历对树中节点进行统计。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
/*** 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 {private int cnt;public void cal(TreeNode root){if(root == null) return ;cnt++;cal(root.left);cal(root.right);}public int countNodes(TreeNode root) {if(root == null) return 0;cnt = 0;cal(root);return cnt;}
}

*思路二：借助完全二叉树性质

题目说明提供的是一颗完全二叉树，因此可以借助完全二叉树性质来减少计算次数。

在一颗完全二叉树中，当一颗子树一直向左走和一直向右走的高度一致，则当前子树是一颗满二叉树。满二叉树的结点公式为：$$2^h-1$$h是树的高度。

当遇到满二叉树的子树直接用公式计算节点数返回可以减少计算。

// java
/*** 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;int leftDepth = 0, rightDepth = 0;TreeNode left = root.left, right = root.right;while(left != null){left = left.left;leftDepth++;}while(right != null){right = right.right;rightDepth++;}// 满二叉树直接用公式计算if(leftDepth == rightDepth){return (2 << leftDepth) - 1;}// 普通树按节点统计return countNodes(root.left) + countNodes(root.right) + 1;}
}