二叉树节点

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

1 前序遍历

1.1 递归遍历

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def helper(root):
            if not root:
                return []
            res.append(root.val)
            helper(root.left)
            helper(root.right)
        res = []
        helper(root)
        return res

1.2 迭代遍历

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = []
        stack = []
        node = root
        while stack or node:
            while node:
                res.append(node.val)
                stack.append(node)
                node = node.left
            node = stack.pop()
            node = node.right
        return res

2 中序遍历

2.1 递归遍历

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        def helper(root):
            if not root:
                return []
            helper(root.left)
            res.append(root.val)
            helper(root.right)
        res = []
        helper(root)
        return res

js中序遍历

 */
var inorderTraversal = function(root) {
    var res = [];
    const inorder = (root) => {
        if (!root) {
            return res;
        }
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
    inorder(root);
    return res;
};

2.2迭代遍历

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = []
        stack = []
        node = root
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.val)
            node = node.right
        return res

3 后序遍历

3.1 递归遍历

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        def helper(root):
            if not root:
                return []
            helper(root.left)
            helper(root.right)
            res.append(root.val)
        res = []
        helper(root)
        return res

3.2 迭代遍历

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = []
        stack = []
        node = root
        while stack or node:
            while node:
                res.append(node.val)
                stack.append(node)
                node = node.right
            node = stack.pop()
            node = node.left
        return res[::-1]

4 层序遍历

import collections
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root == None:
            return []
        res = []
        level = []
        queue = collections.deque()
        queue.append(root)
        dummy = TreeNode(-1)
        queue.append(dummy)
        while len(queue) != 0:
            node = queue.popleft()
            if node == dummy:
                res.append(level)
                level = []
                if len(queue) != 0:
                    queue.append(dummy)
            else:
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return res

var levelOrder = function(root) {

    // 自己创建pop函数
    const custonPop = (arr) => {
        if(arr.length != 0) {
            let x = arr[0];
            arr.shift();
            return x;
        }
        return -1;
    }

    if(!root) {
        return [];
    }
    var res = [];
    var leval = [];
    var dummy = TreeNode(-1);
    var queue = [root];
    queue.push(dummy);
    while (queue.length != 0) {
        var node = custonPop(queue);
        if(node === dummy) {
            res.push(leval);
            leval = [];
            if(queue.length != 0) {
                queue.push(dummy);
            }
        } else {
            leval.push(node.val);
            if(node.left) {
                queue.push(node.left);
            }
            if(node.right) {
                queue.push(node.right);
            }
        }
    }
    return res;
};

二叉树算法 leetcoee定向训练