二叉树 6/20 86-90

1.二叉树的最大深度（ LeetCode 104 ）

递归

/** * 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 maxDepth(TreeNode root) {
    
            if(root == null)return 0;
            if (root.left == null && root.right == null)return 1;
            return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
        }
    }

2.二叉树的最小深度（ LeetCode 111 ）

递归

/** * 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 minDepth(TreeNode root) {
    
            if(root == null)return 0;
            if (root.left == null && root.right == null)return 1;
            int lh = minDepth(root.left);
            int rh = minDepth(root.right);
            //最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
            if (lh == 0)return rh + 1;//左边孩子的高度等于0，代表叶子在右边
            if (rh == 0)return lh + 1;
            return Math.min(lh,rh) + 1;
        }
    }

3.二叉树的所有路径（ LeetCode 257 ）

回溯

/** * 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 List<String> binaryTreePaths(TreeNode root) {
    
            List<String> ans = new ArrayList<>();
            dfs(root,ans,new ArrayList<>());
            return ans;
        }
        public void dfs(TreeNode node,List<String> ans,List<String> selected){
    
            if (node == null)return;
            if (node.left == null && node.right == null){
    
                selected.add(node.val + "");
                StringBuilder s = new StringBuilder();
                for (String x:selected
                     ) {
    
                    s.append(x);
                }
                ans.add(s.toString());
            }else {
    
                selected.add(node.val + "->"); 
            }
            dfs(node.left,ans,selected);
            dfs(node.right,ans,selected);
            selected.remove(selected.size() - 1);//回溯
        }
    }

4.平衡二叉树（ LeetCode 110 ）

递归

/** * 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 boolean isBalanced(TreeNode root) {
    
            if (root == null)return true;//递归结束条件
            if (!isBalanced(root.left))return false;//判断左子树是否是平衡二叉树
            if (!isBalanced(root.right))return false;//判断右子树是否是平衡二叉树
            //判断自己是否是平衡二叉树
            return Math.abs(height(root.left) - height(root.right)) <= 1;
        }
        //求节点的高度
        public int height(TreeNode node){
    
            if (node == null)return 0;
            if (node.left == null && node.right == null)return 1;
            return Math.max(height(node.left),height(node.right)) + 1;
        }
    }

5.左叶子之和（ LeetCode 404 ）

/** * 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 {
    
        int ans = 0;
        public int sumOfLeftLeaves(TreeNode root) {
    
            dfs(root,null);
            return ans;
        }
        public void dfs(TreeNode node,TreeNode parent){
    
            if (node == null)return;
            if (node.left == null
                && node.right == null //为叶子节点
                && parent != null //父节点不为空
                && parent.left == node //为左叶子节点
                )ans += node.val;
            dfs(node.left,node);
            dfs(node.right,node);
        }
    }