Binary tree special exercise

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result=[]
        def traversal(root,result):
            if root==None:
                return
            traversal(root.left,result)
            result.append(root.val)
            traversal(root.right,result)
        traversal(root,result)
        return result

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result=[]
        def traversal(root):
            if root==None:
                return
            traversal(root.left)
            result.append(root.val)
            traversal(root.right)
        traversal(root)
        return result

(2) Preorder traversal

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result=[]
        def traversal(root):
            if root==None:
                return
            result.append(root.val)
            traversal(root.left)
            traversal(root.right)
        traversal(root)
        return result

(3) Postorder traversal

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result=[]
        def traversal(root):
            if root==None:
                return
            traversal(root.left)
            traversal(root.right)
            result.append(root.val)
        traversal(root)
        return result

2. Iterative method

(1) Preorder traversal

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result=[]
        if root==None:
            return result
        s=[]
        s.append(root)
        while s:
            root=s.pop()
            result.append(root.val)
            if root.right:s.append(root.right)
            if root.left:s.append(root.left)
        return result

(2) Postorder traversal

Flip after exchanging the order of left and right nodes

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result=[]
        if not root:
            return result
        s=[]
        s.append(root)
        while s:
            root=s.pop()
            result.append(root.val)
            if root.left:s.append(root.left)
            if root.right:s.append(root.right)
        return result[::-1]

(3) Middle order traversal

This kind of thought is still difficult to master

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result=[]
        if not root:
            return []
        s=[]
        cur=root
        while cur or s:
            if cur:
                s.append(cur)
                cur=cur.left
            else:
                cur=s.pop()
                result.append(cur.val)
                cur=cur.right
        return result

III level traversal

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        results=[]
        if not root:
            return results
        from collections import deque
        que=deque([root])
        while que:
            size=len(que)
            result=[]
            for i in range(size):
                top=que.popleft()
                result.append(top.val)
                if top.left:que.append(top.left)
                if top.right:que.append(top.right)
            results.append(result)
        return results

IV 226. Flip binary tree LeetCode (LeetCode CN. Com)

In essence, it is the preorder traversal of the tree

But every time you traverse to a place, you need to exchange its left and right nodes

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        root.left,root.right=root.right,root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

V 101. Symmetric binary tree LeetCode (LeetCode CN. Com)

1. Preorder traversal

Essentially, it is still preorder traversal

First, judge whether the two node values are equal. If they are not equal, they must be asymmetric

If equal, then judge the left and right children separately

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def traversal(r1,r2):
            if not r1 and not r2:
                return True
            if not r1:
                return False
            if not r2:
                return False
            if r1.val!=r2.val:
                return False
            return traversal(r1.left,r2.right) and traversal(r1.right,r2.left)
        return traversal(root.left,root.right)

2. Iterative method

It is still preorder traversal, but it is implemented by stack

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        stack=[]
        stack.append(root.right)
        stack.append(root.left)
        while stack:
            l=stack.pop()
            r=stack.pop()
            if not l and not r:
                continue
            if not l:
                return False
            if not r:
                return False
            if l.val!=r.val:
                return False
            stack.append(l.left)
            stack.append(r.right)
            stack.append(l.right)
            stack.append(r.left)
        return True

Vi 104. Maximum depth of binary tree LeetCode (LeetCode CN. Com)

Depth first search

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
result=0
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        ans=0
        def dfs(root,depth):
            nonlocal ans
            if not root.left and not root.right:
                ans=max(ans,depth)
                return
            if root.left:
                dfs(root.left,depth+1)
            if root.right:
                dfs(root.right,depth+1)
        dfs(root,1)
        return ans

VII 111. Minimum depth of binary tree LeetCode (LeetCode CN. Com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        ans=1<<32
        def dfs(root,depth):
            nonlocal ans
            if not root.left and not root.right:
                ans=min(ans,depth)
            if root.left:
                dfs(root.left,depth+1)
            if root.right:
                dfs(root.right,depth+1)
        dfs(root,1)
        return ans

VIII 222. Number of nodes of complete binary tree LeetCode (LeetCode CN. Com)

(1)dfs

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        ans=0
        def dfs(root):
            nonlocal ans
            ans+=1
            if not root.left and not root.right:
                return
            if root.left:
                dfs(root.left)
            if root.right:
                dfs(root.right)
        dfs(root)
        return ans

(2)bfs

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        result=0
        if not root:
            return result
        from collections import deque
        que=deque([root])
        while que:
            size=len(que)
            result+=size
            for i in range(size):
                top=que.popleft()
                if top.left:
                    que.append(top.left)
                if top.right:
                    que.append(top.right)
        return result

(3) Properties of complete binary tree

A complete binary tree is either a full binary tree or a little missing in the lower right corner

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        left=root.left
        right=root.right
        leftlen=0
        rightlen=0
        while left:
            leftlen+=1
            left=left.left
        while right:
            rightlen+=1
            right=right.right
        if rightlen==leftlen:
            return (2<<rightlen)-1
        else:
            return 1+self.countNodes(root.left)+self.countNodes(root.right)

IX 110. Balanced binary tree - LeetCode (LeetCode CN. Com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True

        def getheight(root):
            if not root:
                return 0
            return 1+max(getheight(root.left),getheight(root.right))
        return abs(getheight(root.left)-getheight(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def getheight(root):
            if not root:
                return 0
            lefth=getheight(root.left)
            righth=getheight(root.right)
            if lefth==-1:
                return -1
            if righth==-1:
                return -1
            if abs(lefth-righth)>1:
                return -1
            return 1+max(lefth,righth)
        if getheight(root)==-1:
            return False
        else:
            return True

X 257. All paths of binary tree - LeetCode (LeetCode CN. Com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        result=[]
        path=[]
        if root==None:
            return result
        self.traversal(root,result,path)
        return result
 
    def traversal(self,cur,result,path):
        cur.val=str(cur.val)
        path.append(cur.val)
        if not cur.left and not cur.right:
            ans="->".join(path)
            result.append(ans)
            return
        if cur.left:
            self.traversal(cur.left,result,path)
            path.pop()
        if cur.right:
            self.traversal(cur.right,result,path)
            path.pop()
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        result=[]

        def dfs(root,path):
            nonlocal result
            path.append(str(root.val))
            if not root.left and not root.right:
                result.append("->".join(path))
                return
            if root.left:
                dfs(root.left,path)
            if root.right:
                dfs(root.right,path)
        dfs(root,[])
        return result

Xi 100. The same tree LeetCode (LeetCode CN. Com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val!=q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

XII 404. LeetCode (LeetCode CN. Com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        if not root:
            return 0
        ans=0
        def dfs(root):
            nonlocal ans
            if root.left!=None and  root.left.left==None and  root.left.right==None:
                ans+=root.left.val
            if root.left:
                dfs(root.left)
            if root.right:
                dfs(root.right)
            return
        dfs(root)
        return ans

XIII 404. LeetCode (LeetCode CN. Com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        if root==None:
            return 0
        ans=0
        s=[]
        s.append(root)
        while s:
            top=s.pop()
            if top.left and not top.left.left and not top.left.right:
                ans+=top.left.val
            if top.left:
                s.append(top.left)
            if top.right:
                s.append(top.right)
        return ans

XIV 513. Find the value in the lower left corner of the tree - LeetCode (leetcode-cn.com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        ans=0
        maxdepth=-1
        def dfs(root,depth):
            nonlocal ans
            nonlocal maxdepth
            if depth>maxdepth:
                maxdepth=depth
                ans=root.val
            if root.left:
                dfs(root.left,depth+1)
            if root.right:
                dfs(root.right,depth+1)
        dfs(root,1)
        return ans

XV 112. Path sum - LeetCode (LeetCode CN. Com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        def dfs(root,sums):
            sums+=root.val
            if sums==targetSum and not root.left and not root.right:
                return True
            if not root.left and not root.right:
                return False
            a=False
            b=False
            if root.left:a=dfs(root.left,sums)
            if root.right:b=dfs(root.right,sums)
            return a or b
        return dfs(root,0)

XVI 113. Path summation II - LeetCode (LeetCode CN. Com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        result=[]
        if not root:
            return result
        def dfs(root,path,sums):
            nonlocal result
            # path.append(root.val)
            # sums+=root.val
            cursum=sums+root.val
            if not root.left and not root.right:
                if cursum==targetSum:
                    result.append(path+[root.val])
                return
            if root.left:
                dfs(root.left,path+[root.val],sums+root.val)
            if root.right:
                dfs(root.right,path+[root.val],sums+root.val)
        dfs(root,[],0)
        return result

XVII 106. Construct the binary tree LeetCode (leetcode-cn.com) from the middle order and post order traversal sequences

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder:
            return None
        rootnode=postorder[-1]
        root=TreeNode(rootnode)
        index=inorder.index(rootnode)

        leftin=inorder[:index]
        rightin=inorder[index+1:]
        leftpost=postorder[:len(leftin)]
        rightpost=postorder[len(leftin):-1]

        root.left=self.buildTree(leftin,leftpost)
        root.right=self.buildTree(rightin,rightpost)
        return root

XVIII 654. Maximum binary tree - LeetCode (LeetCode CN. Com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        rootnode=max(nums)
        index=nums.index(rootnode)
        root=TreeNode(rootnode)
        root.left=self.constructMaximumBinaryTree(nums[:index])
        root.right=self.constructMaximumBinaryTree(nums[index+1:])
        return root

XIX 617. Merged binary tree LeetCode (LeetCode CN. Com)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1:
            return root2
        if not root2:
            return root1
        root1.val+=root2.val
        root1.left=self.mergeTrees(root1.left,root2.left)
        root1.right=self.mergeTrees(root1.right,root2.right)
        return root1

Keywords: leetcode linked list Binary tree

Added by hackerkts on Thu, 27 Jan 2022 16:10:36 +0200

Programming VIP

Binary tree special exercise

I Recursive traversal

(1) Middle order traversal

(2) Preorder traversal

(3) Postorder traversal

2. Iterative method

(1) Preorder traversal

(2) Postorder traversal

(3) Middle order traversal

III level traversal

IV 226. Flip binary tree LeetCode (LeetCode CN. Com)

V 101. Symmetric binary tree LeetCode (LeetCode CN. Com)

1. Preorder traversal

2. Iterative method

Vi 104. Maximum depth of binary tree LeetCode (LeetCode CN. Com)

VII 111. Minimum depth of binary tree LeetCode (LeetCode CN. Com)

VIII 222. Number of nodes of complete binary tree LeetCode (LeetCode CN. Com)

(1)dfs

(2)bfs

(3) Properties of complete binary tree

IX 110. Balanced binary tree - LeetCode (LeetCode CN. Com)

X 257. All paths of binary tree - LeetCode (LeetCode CN. Com)

Xi 100. The same tree LeetCode (LeetCode CN. Com)

XII 404. LeetCode (LeetCode CN. Com)

XIII 404. LeetCode (LeetCode CN. Com)

XIV 513. Find the value in the lower left corner of the tree - LeetCode (leetcode-cn.com)

XV 112. Path sum - LeetCode (LeetCode CN. Com)

XVI 113. Path summation II - LeetCode (LeetCode CN. Com)

XVII 106. Construct the binary tree LeetCode (leetcode-cn.com) from the middle order and post order traversal sequences

XVIII 654. Maximum binary tree - LeetCode (LeetCode CN. Com)

XIX 617. Merged binary tree LeetCode (LeetCode CN. Com)

Popular Keywords