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

题目：110. 平衡二叉树

文章：12. 平衡二叉树

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

【思路】

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

高度？深度？

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

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

本题求深度，采用后序遍历（左右中） + 递归

  • Java实现
    • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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实现

    • 递归实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    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实现

    • 递归实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String>res = new ArrayList<>();
            if(root == null)return res;
            List<Integer>path = new ArrayList<>();
            traversal(root,path,res);
            return res ;
        }
        //
        public void traversal(TreeNode node ,List<Integer> path,List<String> res){
            //中
            path.add(node.val);
            if(node.left == null && node.right == null){
                StringBuffer sb = new StringBuffer();
                for(int i = 0;i<path.size()-1;i++){
                    sb.append(path.get(i)).append("->");
                }
                sb.append(path.get(path.size()-1));
                res.add(sb.toString());
                return ;
            }
            //左
            if(node.left != null){
                traversal(node.left,path,res);
                //弹出已经加入结果集的答案
                path.remove(path.size()-1);
            }
            if(node.right != null){
                traversal(node.right,path,res);
                //弹出已加入结果集的答案
                path.remove(path.size()-1);
            }
            return;
            //右
        }
    }

  • Go实现

    • 递归实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    func binaryTreePaths(root *TreeNode) []string {
        //需要根节点指向左右节点，因此使用前序遍历（中左右）
        //同时，访问完当前节点后，需要回溯到前一个节点，因此我们需要使用递归
        var traversal func(node *TreeNode,s string)
        res := []string{}
        traversal = 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{
                traversal(node.Left,s)
            } 
            if node.Right != nil{
                traversal(node.Right,s)
            }
            return 
        }
        traversal(root,"")
        return res
    }

404.左叶子之和

文章：15. 左叶子之和

题目：404. 左叶子之和

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

【思路】

递归三部曲：

1.确定递归函数的参数与返回值

2.确定终止条件

3.确定单层递归的逻辑

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

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
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实现
1
2
3
4
5
6
7
8
9
10
11
12
13
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() ：将整型变量转化为字符串型变量