算法学习Day12——二叉树3

完全二叉树

使用后序遍历

先算左右子树的深度，如果相同，就是慢二叉树，直接用公式，2^n-1.

如果不相同，则是左右子树的节点个数向上传递。因为最终肯定会是完全二叉树。

Java左右子树中间是.

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null) return 0;

        TreeNode leftNode=root.left;
        TreeNode rightNode=root.right;
        int leftDepth = 0;
        int rightDepth = 0;
        while (leftNode != null) {
            leftNode = leftNode.left;
            leftDepth++;
        }
        while (rightNode != null) {
            rightNode = rightNode.right ;
            rightDepth++;
        }
        if(leftDepth==rightDepth){
            return (2<<leftDepth)-1;
        }
        int leftNum = countNodes(root.left);
        int rightNum =countNodes(root.right);
        return leftNum + rightNum +1;
    }
    
}

平衡二叉树

使用后序遍历

调用数学函数Math.的形式

class Solution {
    public boolean isBalanced(TreeNode root) {
        int result=getHeight(root);
        if(result==-1) return false;
        else return true;
    }
    public int getHeight(TreeNode node){
        if(node==null) return 0;
        int leftHeight=getHeight(node.left);
        if(leftHeight == -1) return -1;
        int rightHeight =getHeight(node.right);
        if(rightHeight == -1) return -1;
        if(Math.abs(leftHeight-rightHeight)>1) return -1;
        else return 1+Math.max(leftHeight,rightHeight);
    }
}

二叉树的所有路径

使用前序遍历

未精简代码如下，注意输出格式

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if(root==null) return res;
        List<Integer> paths = new ArrayList<>();
        traversal(root,paths,res);
        return res;
    }
    public void traversal(TreeNode node,List<Integer> paths,List<String> res){
        paths.add(node.val);
        if (node.left == null && node.right == null) {
            // 输出
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < paths.size() - 1; i++) {
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));
            res.add(sb.toString());
            return;
        }
        if (node.left != null) {
            traversal(node.left, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
        if (node.right != null) {
            traversal(node.right, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }

    }
}

左叶子之和

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
         if (root == null) return 0;
        int leftValue = sumOfLeftLeaves(root.left);    // 左
        int rightValue = sumOfLeftLeaves(root.right);  // 右
                                                       
        int midValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) { 
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;  // 中
        return sum;

    }
}

找树左下角的值

class Solution {
   private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,0);
        return value;
    }

    private void findLeftValue (TreeNode root,int deep) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        if (root.left != null) findLeftValue(root.left,deep + 1);
        if (root.right != null) findLeftValue(root.right,deep + 1);
    }
}

路径总合

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        targetSum -= root.val;
        if (root.left == root.right) { // root 是叶子
            return targetSum == 0;
        }
        return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
    }
}