算法题（八）--相同的树

本文主要是介绍算法题（八）--相同的树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

解法一、广度优先

思路：每棵树维护一个栈，栈里面用来记录没一层节点的值，如果没一层节点的值相同，则代表是结构和值都相同，如果不符合就代表不是相同的树，直接跳出循环。

代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        def find_level_vale(list_node):
            temp = [];temp_node = []
            for item in list_node:
                if item != None:
                    temp.append(item.val)
                    temp_node.append(item.left)
                    temp_node.append(item.right)
                else:
                    temp.append("none")
            return temp,temp_node

        stack_1 = [];stack_2 = []
        stack_1.append(p);stack_2.append(q)
        while stack_1:
            temp1,temp1_node = find_level_vale(stack_1)
            temp2,temp2_node = find_level_vale(stack_2)
            if temp1 != temp2:
                return False
            stack_1 = temp1_node
            stack_2 = temp2_node
        return True
        

解法二、深度优先

思路：维护一个栈，判断栈中每个节点的最深树结构和值是否相同，如果不同就结束判断。前序、中序、后序遍历都是深度优先算法的一种，因此可以选择一种作为实现方案。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p == None and q == None:
            return True
        else:
            return False
        def inner_left(node,stack):
            while node.left != None:
                stack.append(node.left)
        stack1 = [];stack2 = []
        stack1.append(p);stack2.append(q)
        inner_left(p,stack1);inner_left(q,stack2)
        while stack1:
            temp1 = stack1.pop()
            temp2 = stack2.pop()
            if temp1.val != temp2.val:
                return False
            if temp1.right != None:
                inner_left(temp1.right,stack1)
            if temp2.right != None:
                inner_left(temp2.right,stack2)
        return True
        

这篇关于算法题（八）--相同的树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！