Python 求二叉树路径总和

柔情只为你懂 2022-03-08 09:29 261阅读 0赞

题目来源：

> LeetCode113 路径总和
> 
> 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
> 
> **说明:** 叶子节点是指没有子节点的节点。
> 
>     5
>                  / \
>                 4   8
>                /   / \
>               11  13  4
>              /  \    / \
>             7    2  5   1

借这道题弄懂了二叉树的实现(Java、Python)以及深度遍历、树的递归

#_*_coding:utf-8_*_
    
    
    class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    
    class Solution(object):
        def pathSum(self, root, sum):
            result = []
            self.help(root, sum, [], result)
            return result
    
        def help(self, root, sum, path, result):
            if root is None:
                return
            
            #步骤类似先序遍历
            path.append(root.val)
            #遍历根节点
            if root.left is None and root.right is None:
                if sum == root.val:
                    result.append(list(path))
            #遍历左子树
            self.help(root.left, sum - root.val, path, result)
            #遍历右子树
            self.help(root.right, sum - root.val, path, result)
            path.pop()
    
    root = TreeNode(5)
    l1 = TreeNode(4)
    r1 = TreeNode(8)
    root.left = l1
    root.right = r1
    l2 = TreeNode(11)
    r2 = TreeNode(13)
    r3 = TreeNode(4)
    l1.left = l2
    r1.left = r2
    r1.right = r3
    l3 = TreeNode(7)
    l4 = TreeNode(2)
    r4 = TreeNode(5)
    r5 = TreeNode(1)
    l2.left = l3
    l2.right = l4
    r3.left = r4
    r3.right = r5
    
    slu = Solution()
    
    t = slu.pathSum(root,22)
    print(t)

总结下写递归的思路，以这道题为例：先在根节点的左子树遍历，直到叶子节点；此时递归时root(叶子节点)为None，return后跳出这次递归，进入下一个( self.help(root.right, sum - root.val, path, result) ),结果也是None，也跳出递归，接着到了path.pop(),这个就是回溯法的回退，当前路径不合适(\[5,4,11,7\])，最后的list中的7pop删除，root回到11；接着递归，回退到4，5，这时整个左子树都结束了，最上层的(  self.help(root.left, sum - root.val, path, result) )递归结束，转到右子树开始新的递归，依此类推下去。

如果有朋友觉得我说的不清楚，copy代码debug一下就清楚了，自己跟着程序走一遍流程比什么都好懂。

> 以前一直不明白在树的问题上递归时一种很好的解决方式，但是思路说的头头是道，就是上手写不出来代码，出去面试错失了多少机会。这次总算对这一知识点有了一定的了解，希望越努力越幸运。

## leetcode 236 最近公共祖先问题 ##

> 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
> 
> [百度百科][Link 1]中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。”
> 
>     输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
>     输出: 3
>     解释: 节点5和节点1的最近公共祖先是节点3。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmd5YW5nX3lhbmdxaQ_size_16_color_FFFFFF_t_70][]

class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            // LCA 问题，查阅相关资料
            if (root == null) {
                return root;
            }
            if (root == p || root == q) {
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
    ##################################
            if (left != null && right != null) {
                return root;
            } else if (left != null) {
                return left;
            } else if (right != null) {
                return right;
            }
            return null;
        }
    }

整个递归流程的思路：

从根节点起：

1、这个节点是否为空

2、这个节点是否是p或者q中的一个

3、以上两种都不是的情况下按先序遍历遍历左子树、右子树

4、\#\#\#\#\#\#\#\#\#\#\#\#\#下面的步骤是遍历到叶子节点后才会执行到此(叶子节点递归执行后跳出执行)

if (left != null && right != null) {
                return root;

返回的是根节点，root是最优公共祖先

[Link 1]: https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmd5YW5nX3lhbmdxaQ_size_16_color_FFFFFF_t_70]: /images/20220308/8fb76a1387cd4838a655b9fc15715f53.png