110.平衡二叉树（递归法）

题目：110. 平衡二叉树

文章：12. 平衡二叉树

视频：后序遍历求高度，高度判断是否平衡 | LeetCode：110.平衡二叉树_哔哩哔哩_bilibili

【思路】

平衡二叉数：任何节点的左右子树的高度差不超过1

高度？深度？

高度：距离叶子节点的距离后序遍历，层层向上返回高度+1

深度：距离根节点的距离前序遍历，层次向下+1

采用后序遍历

Java实现
- 递归

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

Go实现

递归实现

func isBalanced(root *TreeNode) bool {
    return getHeight(root) != -1
}

func getHeight(node *TreeNode)(res int){
    if node == nil{
        return 0
    }
    leftHeight := getHeight(node.Left)
    if leftHeight == -1{
        return -1
    }
    rightHeight := getHeight(node.Right)
    if rightHeight == -1{
        return -1
    }
    if abs(leftHeight,rightHeight) >1{
        res = -1
    }else{
        res = 1 + max(leftHeight,rightHeight)
    }
    return 
}
func abs(leftHeight,rightHeight int)(res int){
    if leftHeight > rightHeight{
        return leftHeight-rightHeight
    }else{
        return rightHeight - leftHeight
    }
}
func max(leftHeight,rightHeight int)(res int){
    if leftHeight > rightHeight{
        return leftHeight
    }else{
        return rightHeight
    }
}

257.二叉树的所有路径

题目：257. 二叉树的所有路径

文章：13. 二叉树的所有路径

视频：递归中带着回溯，你感受到了没？| LeetCode：257. 二叉树的所有路径_哔哩哔哩_bilibili

【思路】

由于该题目需要使用父节点指向左右子节点，因此我们需要使用前序遍历对二叉树进行遍历。

回溯

1.递归函数的参数以及返回值

2.确定递归终止条件

3.确定单层递归逻辑

Java实现

递归实现

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 root,List<Integer>paths,List<String> res){
        //前序遍历：中
        paths.add(root.val);
        if(root.left == null &&root.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());//收集一个路径h
            return ;
        }
        if(root.left != null){
            traversal(root.left,paths,res);
            paths.remove(paths.size()-1);
        }
        if(root.right != null){
            traversal(root.right,paths,res);
            paths.remove(paths.size()-1);
        }
    }
}

Go实现

递归实现

func binaryTreePaths(root *TreeNode)  []string {
    res := make([]string,0)
    var travel func(node *TreeNode, s string)
    travel = func(node *TreeNode, s string){
        if(node.Left == nil &&node.Right == nil){
            v := s + strconv.Itoa(node.Val)
            res = append(res,v)
            return
        }
        s = s + strconv.Itoa(node.Val)+"->"
        if node.Left != nil{
            travel(node.Left,s)
        }
        if node.Right != nil{
            travel(node.Right,s)
        }
    }
    travel(root,"")
    return res 
}

404.左叶子之和

文章：15. 左叶子之和

题目：404. 左叶子之和

视频：二叉树的题目中，总有一些规则让你找不到北 | LeetCode：404.左叶子之和_哔哩哔哩_bilibili

【思路】

首先我们需要分清楚左叶子是什么：1.是叶子节点 2.是左边的叶子节点

Java实现

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null)return 0;
        int leftNum = sumOfLeftLeaves(root.left);
        if(root.left!=null && root.left.left==null && root.left.right == null){
            leftNum += root.left.val;
        }
        int rightNum = sumOfLeftLeaves(root.right);
        return leftNum + rightNum;
    }
}

Go实现

func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil{
        return 0
    }
    leftValues := sumOfLeftLeaves(root.Left)
    if root.Left != nil &&root.Left.Left == nil &&root.Left.Right==nil{
        leftValues = root.Left.Val
    }

    rightValues := sumOfLeftLeaves(root.Right)

    return leftValues+rightValues
}

【算法总结】

回溯三部曲

1.递归函数的参数以及返回值

2.确定递归终止条件

3.确定单层递归逻辑

平衡二叉树：需要分清楚二叉树的高度和深度两个概念，采用递归的方法，利用三部曲确定好返回值，该题采用高度，并且会使用到父节点，因此我们采用后序遍历。
二叉树的所有路径：需要使用回溯算法进行解决，需要利用父节点的左右子节点，因此我们采用前序遍历。
左叶子之和：需要使用递归方法进行解决，理解好左叶子的概念，因此我们采用中序遍历。

【语法总结】

Java

StringBuilder |remove()|append()
Go

strconv.Itoa() ：将整型变量转化为字符串型变量