算法刷题笔记 (6) 字符串相加 二叉树的最近公共祖先

字符串相加

字符串相加

解题思路

模拟十进制的加法运算，从低位到高位各位依次相加，其中：

• 本位和sum = 当前位相加结果 + 上一位的进位c
• 最终结果res = sum%10 + res
• 对下一位的进位c = sum/10

解题代码

func addStrings(num1 string, num2 string) string {
    var res string  // 计算结果
    var c int // 上一位的进位
    
    for i, j:= len(num1)-1, len(num2)-1; i>=0 || j>=0; i, j = i-1, j-1 {
        var n1, n2 int  // 当前位
        var sum int //本位和
        if i >= 0 {
            n1 = int(num1[i]-'0')
        }   // else{n1 = 0}
        if j >= 0 {
            n2 = int(num2[j]-'0')
        }   // else{n2 = 0}
        sum = c + n1 + n2   // 计算本位和
        res = string(sum%10+int('0')) + res  // 结果加在前面
        c = sum/10  // 下一位进位
    }

    if c != 0 { // 加上最高位进位
        res = string(c+int('0')) + res
    }

    return res
}

二叉树的最近公共祖先

二叉树的最近公共祖先

解题思路

1. 利用二叉树后续递归遍历解决，如果root为节点p、q的最近公共祖先，可以分为以下几种情况：

   • p和q在root的子树中，并且p和q在root的异侧
   • p=root，且q在root的左/右子树中
   • q=root，且p在root的左/右子树中

   递归返回：

   • 当前的根节点是q或q中任意一个，就返回
   • 根节点不是p和q中任意一个，继续往左右子树中递归查找p和q
   • 若左子树没有p或者q，就返回右子树结果
   • 若右子树没有p或者q，就返回左子树结果
   • 若左右子树都找到了p和q，说明p和q在当前根节点的左右子树上，当前根节点就是最近公共祖先

解题代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        // 若当前根节点为p或者q，直接返回（最近公共祖先不会比当前根更低）
        return root
    }

    // 递归的在左右子树中查找
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    if left == nil {
        // 左子树没有p或者q，返回右子树
        return right
    }

    if right == nil {
        // 左子树没有p或者q，返回左子树
        return left
    }

    // p和q分别在左右子树上，当前根节点就是最近公共祖先
    return root
}