leetcode刷题-二叉树02

102.层序遍历–十题

代码随想录文档讲解
LeetCode102

图论中的深度搜索和广度搜索分别对应二叉树中的递归遍历和层序遍历。

  	3
   /   \
  9		20
  		/	\
  	  15	 7

返回层序遍历结果：

[
[3],
[9, 20],
[15, 7]
]

依赖队列完成，每一层要记录队列中的size，以便后续弹出元素

伪代码c++：

queue<TreeNode*> que;
if(root != NULL) que.push(root);
while( ! que){
	size = que.size();
	vector<int> vec;
	while(size--){
		node = que.front();
		que.pop();
		vec.push_back(node->val);
		if(node->left) que.push(node->left);
		if(node->right) que.push(right->right);
	}
	result.push_back(vec);
}

python代码：

python collections.deque()简介

from collections import deque
str = 'abcd'
dstr = deque(str)
# dstr :  deque(['a', 'b', 'c', 'd'])

# append() ： 从右端添加元素,与list相同
dstr.append(4)
# dstr :  deque(['a', 'b', 'c', 'd', 4])

# appendleft() ： 从左端添加元素
dstr.appendleft(3)
# dstr :  deque([3, 'a', 'b', 'c', 'd', 4])

# pop(): 移除列表中的一个元素（默认最右端的一个元素），并且返回该元素的值（与list同），如果没有元素，将会报出IndexError
# popleft():移除列表中的一个元素（默认最左端的一个元素），并且返回该元素的值，如果没有元素，将会报出IndexError

# 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
from collections import deque
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue = deque([root])
        result = []
        while queue:
            level = []
            size = len(queue)
            while size :
                cur = queue.popleft()
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
                size -= 1
            result.append(level)
        return result

相关题目：LeetCode：102、104、107、111（前面已完成）、116、117、199、429、515、637

226.翻转二叉树

leetcode题目链接
代码随想录文档讲解

题目描述：

思路：

其实就是两两交换节点的左右孩子。
想清楚这道题目应该用哪种遍历方式：递归（前、中、后序）？非递归？
本题使用前序或者后序最为方便。

伪代码（C++）：

# 递归：递归三部曲
TreeNode* invertTree(root){
	if(root==NULL) return root;
	// 前序遍历 根左右
	swap(root->left, root->right);
	invertTree(root->left);
	invertTree(root->right);
}

python代码：

# 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: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

101.对称二叉树

leetcode题目链接
代码随想录文档讲解

思路：

不能判断左右孩子是否相等，应该判断根节点的左子树和右子树是否可以相互翻转，↑翻转二叉树。
其实比较的是外侧的节点是否相等，内侧的节点是否相等，如下图：

确定遍历顺序：只能使用后序遍历（左右根），因为要不断收集左右孩子的信息返回给上一个节点。

伪代码（C++）：

bool compare(TreeNode* left, TreeNode* right){
	if(left==NULL && right!=NULL) return false;
	else if(left!=NULL && right==NULL) return false;
	else if(left==NULL && right==NULL) return true;
	else if(left->val != right->val) return false;
	bool outside = compare(left->left, right->right);
	bool inside = compare(left->right, right->left);
	return outside && inside
}

python代码：

# 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: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.compare(root.left, root.right)

    def compare(self, left, right):
        if(left == None and right != None):
            return False
        elif(left != None and right == None):
            return False
        elif(left == None and right == None):
            return True
        elif(left.val != right.val):
            return False
        outside = self.compare(left.left, right.right)
        inside = self.compare(left.right, right.left)
        return outside and inside

除此之外，也可使用迭代法（队列、栈都可）