LeetCode刷题笔记6

二叉树的遍历

==首先，先复习一下二叉树的遍历：==

样例二叉树图

前序遍历

• 代码实现

  • 递归

    • 实现代码

      def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
          ans = []
          def preOrder(node: Optional[TreeNode]):
              if not node:
                  return []
              ans.append(node)
              preOrder(node.left)
              preOrder(node.right)
          preOrder(root)
          return ans

  • 迭代

    • 思路：使用栈辅助实现非递归。

      由于前序遍历是先对当前节点进行操作，再遍历当前节点的左子树，最后遍历当前节点的右子树。

      因此在==入栈前进行操作==，随后遍历其左子树——即==栈中的点左子树已经被遍历==，当左子树遍历到底的时候，将栈顶pop出来，此时的栈顶元素的左子树已经遍历完毕，开始遍历其右子树，即==出栈遍历右子树==。

    • 实现代码：

      • Python

        def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
            ans, stack = [], []
            cur = root
            while cur or stack:
                while cur:
                    ans.append(cur.val)
                    stack.append(cur)
                    cur = cur.left
                cur = stack.pop()
                cur = cur.right
            return ans

      • Typescript

        function preorderTraversal(root: TreeNode | null): number[] {
            const ans = <number[]>[];
            const stack = <TreeNode[]>[];
            let cur = root;
            while(cur || stack.length) {
                while(cur) {
                    ans.push(cur.val);
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();
                cur = cur.right;
            }
            return ans;
        }

中序遍历

• 代码实现

  • 递归

    • 实现代码

      def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
          ans = []
          def inOrder(node: Optional[TreeNode]):
              if not node:
                  return []
              inOrder(node.left)
              ans.append(node)
              inOrder(node.right)
          inOrder(root)
          return ans

  • 迭代

    • 思路：使用栈辅助实现非递归，与前序遍历非递归十分类似。

      由于中序遍历是先对当前节点的左子树进行操作，再对当前节点进行操作，最后遍历当前节点的右子树。

      因此先进行入栈操作，遍历其左子树——即==栈中的点左子树已经被遍历==，当左子树遍历到底的时候，将栈顶pop出来，==出栈后进行操作==，随后，此时的栈顶元素的左子树已经遍历完毕，开始遍历其右子树，即==操作后遍历右子树==。

    • 实现代码：

      • Python

        def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
            ans, stack = [], []
            cur = root
            while cur or stack:
                while cur:
                    stack.append(cur)
                    cur = cur.left
                cur = stack.pop()
                ans.append(cur.val)
                cur = cur.right
            return ans

      • Typescript

        function preorderTraversal(root: TreeNode | null): number[] {
            const ans = <number[]>[];
            const stack = <TreeNode[]>[];
            let cur = root;
            while(cur || stack.length) {
                while(cur) {
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();
                ans.push(cur.val);
                cur = cur.right;
            }
            return ans;
        }

后序遍历

• 代码实现

  • 递归

    • 实现代码

      def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
          ans = []
          def inOrder(node: Optional[TreeNode]):
              if not node:
                  return []
              inOrder(node.left)
              inOrder(node.right)
              ans.append(node)
          inOrder(root)
          return ans

  • 迭代

    • 思路：使用栈辅助实现非递归，与前中序遍历左子树的思路一致，但是在于出栈的时候需要判断是否含有右子树以及右子树是否已经被遍历。

      由于中序遍历是先对当前节点的左子树进行操作，再遍历当前节点的右子树，最后对当前节点进行操作。

      因此先进行入栈操作，遍历其左子树——即==栈中的点左子树已经被遍历==，当左子树遍历到底的时候，将栈顶pop出来时：

      ​ 首先判断该节点是否==还有右子树或者右子树是否已经被完全遍历==，

      ​ 若是，则对该节点进行操作；

      ​ 否则，将该节点==重新入栈==。

      • Python

        def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
            ans, stack = [], []
            cur = root
            prev = None # 用于保存上一个被遍历右子树的节点
            while cur or stack:
                while cur:
                    stack.append(cur)
                    cur = cur.left
                cur = stack.pop()
                if not cur.right or cur.right == prev:
                    ans.append(cur.val)
                    prev = cur
                    cur = None
                else:
                    stack.append(cur)
                    cur = cur.right
        	return ans

      • Typescript

        function postorderTraversal(root: TreeNode | null): number[] {
            const stack = <TreeNode[]>[];
            const ans = <number[]>[];
            
            let prev = undefined;
        
            while(root || stack.length) {
                while(root){
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if(!root.right || root.right === prev) {
                    ans.push(root.val);
                    prev = root;
                    root = undefined;
                }
                else {
                    stack.push(root);
                    root = root.right;
                }
            }
            return ans;
        };

LeetCode 剑指Offer

剑指 Offer 32 - I. 从上到下打印二叉树（层次遍历）

• 题目描述

  从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

• 代码实现

  • 迭代

    • 思路：用队列作为辅助空间，队列初始化为[root]，每次出队的时候，对出队的节点进行操作，然后将出队的节点的子节点一同入队（若有），循环直至队列为空。

      • Python

        def levelOrder(root: TreeNode) -> List[int]:
            if not root:
                return []
            ans, queue = [], [root]
            while queue:
                cur = queue.pop(0)
                ans.append(cur.val)
                if cur.left:
                    queue.push(cur.left)
                if cur.right:
                    queue.push(cur.right)
            return ans

      • Typescript

        function levelOrder(root: TreeNode | null): number[] {
            if(!root){
                return []
            }
            const ans = <number[]>[];
            const queue = <TreeNode[]>[root];
            
            while(queue.length) {
                let cur = queue.shift();
                ans.push(cur.val);
                if(cur.left)
                    queue.push(cur.left);
                if(cur.right)
                    queue.push(cur.right);
            }

剑指 Offer 32 - II. 从上到下打印二叉树 II

题目描述

​ 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

• 实例

  例如:
  给定二叉树: [3,9,20,null,null,15,7],
  
      3
     / \
    9  20
      /  \
     15   7
  返回其层次遍历结果：
  
  [
    [3],
    [9,20],
    [15,7]
  ]

• 提示

  • 节点总数 <= 1000

解题思路

​ 事实上还是二叉树的层次遍历，与直接存储节点的值稍微不一样的地方在于，需要按不同层次进行分类。

具体思路为以下几点：

1. 队列中存储的值不仅是节点的值，同时将节点的层次一并存储；
2. 而返回的ans不单纯是一个List而是一个==哈希表(字典)==，以下标作为key，节点的值作为value；
3. 由于每次进行出队操作，都需要添加出队节点的左子树与右子树（若存在），所以新节点入队时候将额外带上出队的层次+1；
4. 最后出队的值会判断是否存在当前层次的value，若没有则ans当前层次初始化一个，若有则ans[当前层次].append()。

实现代码

1. Python

   class Solution:
       def levelOrder(self, root: TreeNode) -> List[List[int]]:
           if not root:
               return []
           ans, queue = [], [[root, 0]]
           
           while queue:
               item = queue.pop(0)
               cur = item[0]
               pos = item[1]
               if cur.left:
                   queue.append([cur.left, pos + 1])
               if cur.right:
                   queue.append([cur.right, pos + 1])
               
               if len(ans) <= pos:
                   ans.append([cur.val])
               else:
                   ans[pos].append(cur.val)
   
           return ans

2. JS/TS

   function levelOrder(root: TreeNode | null): number[][] {
       if(!root)
       	return []
       const ans = <number[][]>[];
       const queue = [[root, 0]];
   
       while(queue.length) {
           let item = queue.shift();
           let cur = <TreeNode>item[0];
           let pos = <number>item[1];
   
           if(cur.left){
               queue.push([cur.left, pos+1]);
           }
           if(cur.right){
               queue.push([cur.right, pos+1]);
           }
   
           if(ans.length<=pos){
               ans.push([cur.val]);
           }
           else{
               ans[pos].push(cur.val);
           }
       }
   
       return ans; 
   };

剑指 Offer 32 - III. 从上到下打印二叉树 III

题目描述

​ 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

• 实例

  例如:
  给定二叉树: [3,9,20,null,null,15,7],
  
      3
     / \
    9  20
      /  \
     15   7
  返回其层次遍历结果：
  
  [
    [3],
    [20,9],
    [15,7]
  ]

• 提示

  • 节点总数 <= 1000

解题思路

​ 步骤与第二题几乎完全一致，最后对ans进行一个简单的处理，倒转所有下标为奇数的列表即可。

实现代码

1. Python

   class Solution:
       def levelOrder(self, root: TreeNode) -> List[List[int]]:
           if not root:
               return []
           ans, queue = [], [[root, 0]]
           
           while queue:
               item = queue.pop(0)
               cur = item[0]
               pos = item[1]
               if cur.left:
                   queue.append([cur.left, pos + 1])
               if cur.right:
                   queue.append([cur.right, pos + 1])
               
               if len(ans) <= pos:
                   ans.append([cur.val])
               else:
                   ans[pos].append(cur.val)
   
           for index, a in enumerate(ans):
               if index%2:
                   a.reverse()
   
           return ans

2. Typescript

   function levelOrder(root: TreeNode | null): number[][] {
       if(!root)
       	return []
       const ans = <number[][]>[];
       const queue = [[root, 0]];
   
       while(queue.length) {
           let item = queue.shift();
           let cur = <TreeNode>item[0];
           let pos = <number>item[1];
   
           if(cur.left){
               queue.push([cur.left, pos+1]);
           }
           if(cur.right){
               queue.push([cur.right, pos+1]);
           }
   
           if(ans.length<=pos){
               ans.push([cur.val]);
           }
           else{
               ans[pos].push(cur.val);
           }
       }
   
       for(let [index,value] of ans.entries()){
           if(index%2){
               value.reverse();
           }
       }
   
       return ans; 
   };