二叉树的递归-层序遍历

labuladong原创约 3623 字

After understanding the Basic Concepts of Binary Trees and Special Types of Binary Trees, this article will explain how to traverse and access nodes in a binary tree.

Recursive Traversal (DFS)

Framework for traversing binary trees:

java 🟢

// basic binary tree node
class TreeNode {
    int val;
    TreeNode left, right;
}

// traversal framework for binary tree
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    traverse(root.left);
    traverse(root.right);
}

cpp 🤖

// basic binary tree node
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// binary tree traversal framework
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    traverse(root->left);
    traverse(root->right);
}

python 🤖

# basic binary tree node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# traversal framework for binary tree
def traverse(root: TreeNode):
    if root is None:
        return
    traverse(root.left)
    traverse(root.right)

go 🤖

// basic binary tree node
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// binary tree traversal framework
func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    traverse(root.Right)
}

javascript 🤖

// basic binary tree node
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// binary tree traversal framework
var traverse = function(root) {
    if (root === null) {
        return;
    }
    traverse(root.left);
    traverse(root.right);
}

Why can this short and concise code traverse a binary tree? And in what order does it traverse the tree?

For a recursive traversal function like traverse, you can think of it as a pointer moving through the structure of the binary tree. Below, I've used a visualization to intuitively show you how this function traverses the binary tree.

Open this visualization panel, and the position of the root pointer on the right indicates the current node being accessed, which is the current position of the traverse function. The orange-yellow section shows the stack of the traverse function. You can click the play button in the upper left corner to observe the changes in the position of the root pointer:

The traversal order of the traverse function is to keep moving to the left child node until it encounters a null pointer and cannot move further, then attempt to move one step to the right child node; then keep trying to move to the left child node again, and so on. If both the left and right subtrees are fully traversed, it returns to the parent node above. Actually, you can see from the code that it first recursively calls root.left, and then recursively calls root.right.

The order of this recursive traversal of nodes is fixed. It is crucial to remember this order; otherwise, you will definitely struggle with the binary tree structure.

Some readers with a background in data structures might ask: "But Dong, anyone who has taken a data structures course in university has heard of pre-order, in-order, and post-order traversals of binary trees, which produce three different result orders. Why do you say the order of recursive traversal of nodes is fixed here?"

This is a good question. First of all, the order of recursive traversal, i.e., the order in which the traverse function accesses nodes, is indeed fixed. However, the effect can be different depending on where you write the code in the traverse function.

For example, when you first enter a node, you don't yet know anything about its child nodes, whereas when you are about to leave a node, you have already traversed all its child nodes. Writing code in these two situations can definitely have different effects.

What you refer to as pre-order, in-order, and post-order traversals are actually just writing code in different positions within the above binary tree traversal framework:

java 🟢

// Binary tree traversal framework
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // pre-order position
    traverse(root.left);
    // in-order position
    traverse(root.right);
    // post-order position
}

cpp 🤖

// binary tree traversal framework
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // pre-order position
    traverse(root->left);
    // in-order position
    traverse(root->right);
    // post-order position
}

python 🤖

# Binary tree traversal framework
def traverse(root):
    if root is None:
        return
    # Pre-order position
    traverse(root.left)
    # In-order position
    traverse(root.right)
    # Post-order position

go 🤖

// Binary tree traversal framework
func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // Preorder position
    traverse(root.Left)
    // Inorder position
    traverse(root.Right)
    // Postorder position
}

javascript 🤖

// binary tree traversal framework
var traverse = function(root) {
    if (root === null) {
        return;
    }
    // pre-order position
    traverse(root.left);
    // in-order position
    traverse(root.right);
    // post-order position
};

The code at the pre-order position executes when entering a node; the code at the in-order position executes after traversing the left subtree and before traversing the right subtree; the code at the post-order position executes after traversing both subtrees:

You can open this visualization panel and try the following operations:

Continuously click on the line preorderResult.push and observe the order in which the root pointer moves on the tree and the elements in preorderResult. This is the pre-order traversal sequence.
Reset the visualization panel, continuously click on the line inorderResult.push, and observe the root pointer's movement and the elements in inorderResult. This is the in-order traversal sequence.
Reset the visualization panel, continuously click on the line postorderResult.push, and observe the root pointer's movement and the elements in postorderResult. This is the post-order traversal sequence.

Understanding the pre-order, in-order, and post-order positions in a binary tree is very important. I will explore the differences and connections between these traversal methods, and how to apply them to backtracking and dynamic programming algorithms in Binary Tree Algorithm Ideas (Overview) and related exercises, so I won't go into depth here.

Some readers might ask, why does this traverse function first recursively traverse root.left and then root.right? Can it be reversed?

Of course, it can be reversed. However, the terms pre-order, in-order, and post-order generally assume left-first traversal. This is a conventional habit. If you insist on traversing right first and then left, your understanding of pre-order, in-order, and post-order traversal will differ from the general consensus, which might increase communication costs. Therefore, unless there is a specific need, it is recommended to follow the left-first convention.

In-order Traversal of BST is Ordered

It is important to emphasize that the in-order traversal result of a Binary Search Tree (BST) is ordered. This is a key property of BSTs.

You can observe this by clicking on the line res.push(root.val); in the visualization panel to see the order in which nodes are accessed during in-order traversal:

In the subsequent BST Exercise Collection, some problems will utilize this property.

Level Order Traversal (BFS)

The above recursive traversal relies on the function stack to recursively traverse the binary tree. If you consider the recursive function traverse as a pointer, then the order in which this pointer moves through the binary tree roughly starts from the far left and goes column by column to the far right.

You can use the visualization panel and click on the line of code if (root == null) to see the order in which the root variable moves through the tree. This will give you a clear view of the order in which the traverse function visits the nodes:

Level order traversal of a binary tree, as the name suggests, means traversing the tree level by level. This traversal method requires the use of a queue, and depending on different needs, there are mainly three different ways to write it. Below are the examples one by one.

Method One

This is the simplest method, and the code is as follows:

java 🟢

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        TreeNode cur = q.poll();
        // visit the cur node
        System.out.println(cur.val);

        // add the left and right children of cur to the queue
        if (cur.left != null) {
            q.offer(cur.left);
        }
        if (cur.right != null) {
            q.offer(cur.right);
        }
    }
}

cpp 🤖

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        // visit the cur node
        std::cout << cur->val << std::endl;
        
        // add the left and right children of cur to the queue
        if (cur->left != nullptr) {
            q.push(cur->left);
        }
        if (cur->right != nullptr) {
            q.push(cur->right);
        }
    }
}

python 🤖

from collections import deque

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    q.append(root)
    while q:
        cur = q.popleft()
        # visit cur node
        print(cur.val)

        # add cur's left and right children to the queue
        if cur.left is not None:
            q.append(cur.left)
        if cur.right is not None:
            q.append(cur.right)

go 🤖

func levelOrderTraverse(root *TreeNode) {
    if root == nil {
        return
    }
    q := []*TreeNode{}
    q = append(q, root)
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        // visit cur node
        fmt.Println(cur.Val)
        
        // add cur's left and right children to the queue
        if cur.Left != nil {
            q = append(q, cur.Left)
        }
        if cur.Right != nil {
            q = append(q, cur.Right)
        }
    }
}

javascript 🤖

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    var q = [];
    q.push(root);
    while (q.length !== 0) {
        var cur = q.shift();
        // visit cur node
        console.log(cur.val);

        // add cur's left and right children to the queue
        if (cur.left !== null) {
            q.push(cur.left);
        }
        if (cur.right !== null) {
            q.push(cur.right);
        }
    }
}

You can open this visualization panel and click on the line of code console.log(cur.val);. You will see that level-order traversal visits the binary tree nodes layer by layer, from left to right:

Pros and Cons of This Approach

The biggest advantage of this approach is its simplicity. You just take the front element out of the queue and then add its left and right children to the queue, that's it.

However, the downside of this approach is that it cannot tell which level the current node is on. Knowing the level of nodes is a common requirement, for example, when you need to collect nodes of each level or calculate the minimum depth of a binary tree.

So, although this approach is simple, it is not used very often. The following method is more commonly used.

Method Two

With a slight modification to the above solution, we get the following approach:

java 🟢

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    // record the current level being traversed (root node is considered as level 1)
    int depth = 1;

    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            // visit the cur node and know its level
            System.out.println("depth = " + depth + ", val = " + cur.val);

            // add the left and right children of cur to the queue
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
        depth++;
    }
}

cpp 🤖

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    // record the current level being traversed (the root node is considered as level 1)
    int depth = 1;

    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            // visit the cur node, knowing its level
            cout << "depth = " << depth << ", val = " << cur->val << endl;

            // add the left and right children of cur to the queue
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
        depth++;
    }
}

python 🤖

from collections import deque

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    q.append(root)
    # record the current depth being traversed (root node is considered as level 1)
    depth = 1

    while q:
        sz = len(q)
        for i in range(sz):
            cur = q.popleft()
            # visit cur node and know its depth
            print(f"depth = {depth}, val = {cur.val}")

            # add cur's left and right children to the queue
            if cur.left is not None:
                q.append(cur.left)
            if cur.right is not None:
                q.append(cur.right)
        depth += 1

go 🤖

func levelOrderTraverse(root *TreeNode) {
    if root == nil {
        return
    }
    q := []*TreeNode{root}
    // record the current depth being traversed (root node is considered as level 1)
    depth := 1

    for len(q) > 0 {
        // get the current queue length
        sz := len(q)
        for i := 0; i < sz; i++ {
            // dequeue the front of the queue
            cur := q[0]
            q = q[1:]
            // visit the cur node and know its depth
            fmt.Printf("depth = %d, val = %d\n", depth, cur.Val)

            // add cur's left and right children to the queue
            if cur.Left != nil {
                q = append(q, cur.Left)
            }
            if cur.Right != nil {
                q = append(q, cur.Right)
            }
        }
        depth++
    }
}

javascript 🤖

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    var q = [];
    q.push(root);
    // record the current depth (root node is considered as level 1)
    var depth = 1;

    while (q.length !== 0) {
        var sz = q.length;
        for (var i = 0; i < sz; i++) {
            var cur = q.shift();
            // visit the cur node and know its depth
            console.log("depth = " + depth + ", val = " + cur.val);

            // add the left and right children of cur to the queue
            if (cur.left !== null) {
                q.push(cur.left);
            }
            if (cur.right !== null) {
                q.push(cur.right);
            }
        }
        depth++;
    }
};

注

Pay attention to the inner for loop in the code:

int sz = q.size();
for (int i = 0; i < sz; i++) {
    ...
}

The variable i keeps track of the current position of the node cur in the current level. In most algorithm problems, you won't need this variable, so you can use the following approach instead:

int sz = q.size();
while (sz-- > 0) {
    ...
}

This is a matter of personal preference.

However, make sure to save the queue length sz before starting the loop, because the length of the queue changes during the loop, and you can't use q.size() directly as the loop condition.

You can open this visualization panel and click on the console.log line of code. You will see that the binary tree nodes are still traversed level by level from left to right, but this time it also prints the level of each node:

This approach can record the level of each node, solving problems like finding the minimum depth of a binary tree. It is our most commonly used level-order traversal method.

Method Three

If Method Two is the most common, why is there a Method Three? It's to lay the groundwork for more advanced content later.

Right now, we're just discussing level-order traversal of a binary tree. However, level-order traversal of a binary tree can extend to level-order traversal of an N-ary tree, BFS traversal of a graph, and the classic BFS brute-force algorithm framework. So, we need to expand a bit here.

Recapping Method Two, every time we traverse down one level, we add 1 to depth. You can think of it as each branch having a weight of 1. The depth of each node in a binary tree is the sum of the path weights from the root to that node. All nodes in the same level have the same path weight sum.

Now, if the path weight sum of each branch can be any value, and you need to perform a level-order traversal of the entire tree and print the path weight sum of each node, how would you do it?

In this case, the path weight sums of nodes in the same level may not be the same. Using Method Two, which maintains only a depth variable, won't meet the requirement.

Method Three solves this problem by adding a State class to Method One, allowing each node to maintain its own path weight sum. Here is the code:

java 🟢

class State {
    TreeNode node;
    int depth;

    State(TreeNode node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<State> q = new LinkedList<>();
    // the path weight sum of the root node is 1
    q.offer(new State(root, 1));

    while (!q.isEmpty()) {
        State cur = q.poll();
        // visit the cur node, while knowing its path weight sum
        System.out.println("depth = " + cur.depth + ", val = " + cur.node.val);

        // add the left and right child nodes of cur to the queue
        if (cur.node.left != null) {
            q.offer(new State(cur.node.left, cur.depth + 1));
        }
        if (cur.node.right != null) {
            q.offer(new State(cur.node.right, cur.depth + 1));
        }
    }
}

cpp 🤖

class State {
public:
    TreeNode* node;
    int depth;

    State(TreeNode* node, int depth) : node(node), depth(depth) {}
};

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<State> q;
    // the path weight sum of the root node is 1
    q.push(State(root, 1));

    while (!q.empty()) {
        State cur = q.front();
        q.pop();
        // visit the cur node, while knowing its path weight sum
        cout << "depth = " << cur.depth << ", val = " << cur.node->val << endl;

        // add the left and right children of cur to the queue
        if (cur.node->left != nullptr) {
            q.push(State(cur.node->left, cur.depth + 1));
        }
        if (cur.node->right != nullptr) {
            q.push(State(cur.node->right, cur.depth + 1));
        }
    }
}

python 🤖

class State:
    def __init__(self, node, depth):
        self.node = node
        self.depth = depth

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    # the path weight sum of the root node is 1
    q.append(State(root, 1))

    while q:
        cur = q.popleft()
        # visit the cur node, and know its path weight sum
        print(f"depth = {cur.depth}, val = {cur.node.val}")

        # add the left and right child nodes of cur to the queue
        if cur.node.left is not None:
            q.append(State(cur.node.left, cur.depth + 1))
        if cur.node.right is not None:
            q.append(State(cur.node.right, cur.depth + 1))

go 🤖

type State struct {
    node  *TreeNode
    depth int
}

func levelOrderTraverse(root *TreeNode) {
    if root == nil {
        return
    }
    q := []State{{root, 1}}

    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        // visit the cur node, also know its path weight sum
        fmt.Printf("depth = %d, val = %d\n", cur.depth, cur.node.Val)

        // add cur's left and right children to the queue
        if cur.node.Left != nil {
            q = append(q, State{cur.node.Left, cur.depth + 1})
        }
        if cur.node.Right != nil {
            q = append(q, State{cur.node.Right, cur.depth + 1})
        }
    }
}

javascript 🤖

function State(node, depth) {
    this.node = node;
    this.depth = depth;
}

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    // @visualize bfs
    var q = [];
    // the path weight sum of the root node is 1
    q.push(new State(root, 1));

    while (q.length !== 0) {
        var cur = q.shift();
        // visit the cur node, while knowing its path weight sum
        console.log("depth = " + cur.depth + ", val = " + cur.node.val);

        // add the left and right children of cur to the queue
        if (cur.node.left !== null) {
            q.push(new State(cur.node.left, cur.depth + 1));
        }
        if (cur.node.right !== null) {
            q.push(new State(cur.node.right, cur.depth + 1));
        }
    }
};

You can open this visual panel and click on the line of code with console.log. This will allow you to see the tree nodes being traversed layer by layer from left to right, along with the level of each node:

With this approach, each node has its own depth variable, which is the most flexible and can meet all BFS algorithm needs. However, defining an additional State class can be cumbersome, so it's usually sufficient to use the second approach unless necessary.

You'll soon learn that scenarios with weighted edges belong to graph algorithms and will be used in the upcoming BFS Algorithm Exercises and Dijkstra's Algorithm.

Other Traversal Methods?

There are only the two traversal methods mentioned above for binary trees. There may be different ways to write them, but fundamentally, they cannot deviate from these two methods.

For instance, you might see code that uses a stack to iteratively traverse a binary tree. However, this is essentially still a recursive traversal, just manually maintaining a stack to simulate the recursive calls.

Similarly, you might see code that recursively traverses a binary tree layer by layer. But this is essentially level order traversal, just presenting the for loop in the level order traversal code in a recursive format.

In summary, don't be confused by appearances. The traversal methods for binary trees are just these two. Once you master these two methods with the following tutorials and exercises, all brute-force algorithms will be a piece of cake.