leetcode-二叉树题解I

二叉树的特点

树是一种十分重要的数据结构，是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。

它具有以下的特点：

• 每个节点都只有有限个子节点或无子节点；

• 没有父节点的节点称为根节点；

• 每一个非根节点有且只有一个父节点；

• 除了根节点外，每个子节点可以分为多个不相交的子树；

• 树里面没有环路。

  因此，树的定义为：

class TreeNode：
	def __init__(self,x):
		self.val=x
         self.left=Null
         self.right=Null
 # NULL可以占位，但是表示空值

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode  (int x)：val(x),left(NULL),right(NULL)
}

了解一个数据结构，必须先学会如何遍历和查找。

遍历二叉树的数据结构有三种方式，分别是前序遍历，中序遍历和后序遍历。代码上的实现非常类似，但要了解里面的原理。

前序遍历：

using namespace std；
class solution{
public:
    vector<int> preorderTravsal(Treenode* root){
        vector<int> res;
        __preorderTraversal(root,res);
        return res;
    }
}    
private:
	void FindBianryTree(TreeNode* Tree, vector<int> &res ){
		if(node){
            res.push_back(node->val);
            __preorderTraversal(node->left,res);
            __preorderTraversal(node->right,res);
        }    
};

中序遍历:

using namespace std；
class solution{
public:
    vector<int> midorderTravsal(Treenode* root){
        vector<int> res;
        __midorderTraversal(root,res);
        return res;
    }
}    
private:
	void FindBianryTree(TreeNode* Tree, vector<int> &res ){
		if(node){
            res.push_back(node->val);
            __midorderTraversal(node->left,res);
            __midorderTraversal(node->right,res);
        }    
};

后序遍历：

using namespace std；
class solution{
public:
    vector<int> aftorderTravsal(Treenode* root){
        vector<int> res;
        __aftorderTraversal(root,res);
        return res;
    }
}    
private:
	void FindBianryTree(TreeNode* Tree, vector<int> &res ){
		if(node){
            res.push_back(node->val);
            __aftorderTraversal(node->left,res);
            __aftorderTraversal(node->right,res);
        }    
};

了解了遍历的基本特点之后，可以解决相关的遍历的算法问题了。

Leetcode404:计算给定二叉树的所有左叶子之和：

计算给定二叉树的所有左叶子之和。

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

使用递归的方法，总和等于左子树的值加上右子树的值，终止条件是当前节点为左子叶或者为空节点。代码如下：

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        if not root:
            return 0
        if root and root.left and not root.left.left and not root.left.right:
            return root.left.val+self.sumOfLeftLeaves(root.right)
        return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

Leetcode100:相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例1:

  输入:    1         1
          / \       / \
         2   3     2   3
  [1,2,3],   [1,2,3]
  输出: true

示例2：

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]
输出: false

使用递归。首先判断 p 和 q 是不是 None，然后判断它们的值是否相等。若以上判断通过，则递归对子结点做同样操作。

class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """ 
        # p and q are both None
        if not p and not q:
            return True
        # one of p and q is None
        if not q or not p:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.right, q.right) and \
               self.isSameTree(p.left, q.left)

leetcode474: 路径总和II

给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

使用单递归dfs：

class Solution:
	def pathSum(self, root: TreeNode, sum: int) -> int:
        if not root:
            return 0

        # sums为node的父节点已能构成的和，返回最长可延伸到node结束的所有路径所能构成的和列表
    def dfs(node, sums):
        left = right = 0  # 左右的值默认为0
        # 之前的和加当前结点值能构成的新和，以及从当前结点开始算的新和
        temp = [num + node.val for num in sums] + [node.val]
        if node.left:
            left = dfs(node.left, temp)  # 递归
        if node.right:
            right = dfs(node.right, temp)  # 递归
        return temp.count(sum) + left + right

    return dfs(root, [])