二叉树心法（思路篇）

114. 二叉树展开为链表 https://leetcode.cn/problems/flatten-binary-tree-to-linked-list

114. Flatten Binary Tree to Linked List https://leetcode.com/problems/flatten-binary-tree-to-linked-list

116. 填充每个节点的下一个右侧节点指针 https://leetcode.cn/problems/populating-next-right-pointers-in-each-node

116. Populating Next Right Pointers in Each Node https://leetcode.com/problems/populating-next-right-pointers-in-each-node

226. 翻转二叉树 https://leetcode.cn/problems/invert-binary-tree

226. Invert Binary Tree https://leetcode.com/problems/invert-binary-tree

剑指 Offer 27. 二叉树的镜像 https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof

剑指 Offer 27. 二叉树的镜像 LCOF https://leetcode.com/problems/er-cha-shu-de-jing-xiang-lcof

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
114. Flatten Binary Tree to Linked List	🟠
116. Populating Next Right Pointers in Each Node	🟠
226. Invert Binary Tree	🟢

Prerequisites

Before reading this article, you need to learn:

• Basic Binary Tree Structure
• DFS/BFS Traversal of Binary Trees
• Dong's Guide to Binary Trees (Overview)

Tip

本文有视频版：Binary Trees/Recursive Framework Thinking (Overview)。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

This article follows Dong's Guide to Binary Trees (Overview), and first restates the general framework for solving binary tree problems summarized in the previous article:

注

The thinking pattern for solving binary tree problems can be divided into two categories:

1. Can the answer be obtained by traversing the binary tree once? If yes, use a traverse function along with external variables to achieve this, which is called the "traversal" thinking pattern.

2. Can a recursive function be defined to derive the answer to the original problem from the answers to subproblems (subtrees)? If yes, write the definition of this recursive function and make full use of its return value, which is called the "problem decomposition" thinking pattern.

Regardless of which thinking pattern you use, you need to consider:

What does a single binary tree node need to do? When does it need to do it (pre-order, in-order, or post-order position)? You don't need to worry about other nodes; the recursive function will execute the same operation on all nodes for you.

This article will use several relatively simple problems as examples to guide you through applying these frameworks, helping you understand the differences and connections between the "traversal" thinking and the "problem decomposition" thinking.

First Problem: Invert a Binary Tree

Let's start with a simple problem, LeetCode problem 226 "Invert Binary Tree". Given the root node root of a binary tree, your task is to invert the entire tree, making it a mirror image. For example, if the input binary tree is:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

The algorithm should invert the tree in place, so that the tree rooted at root becomes:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

It's not hard to see that by swapping the left and right child nodes of every node in the binary tree, the final result will be the completely inverted binary tree.

Now, let's go through the general approach for solving binary tree problems in our minds:

1. Can this problem be solved using a "traversal" mindset?

Yes, I can write a traverse function to visit each node and swap its left and right child nodes.

What does a single node need to do? It needs to swap its left and right child nodes.

When should this be done? It seems that it can be done in pre-order, in-order, or post-order positions.

Based on the above, we can write the following solution code:

java 🟢

class Solution {
    // main function
    public TreeNode invertTree(TreeNode root) {
        // traverse the binary tree, swap the child nodes of each node
        traverse(root);
        return root;
    }

    // binary tree traversal function
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }

        // *** pre-order position ***
        // what each node needs to do is to swap its left and right children
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        // traversal framework, go traverse the nodes of the left and right subtrees
        traverse(root.left);
        traverse(root.right);
    }
}

cpp 🤖

class Solution {
public:
    // main function
    TreeNode* invertTree(TreeNode* root) {
        // traverse the binary tree, swap the child nodes of each node
        if(root != NULL) traverse(root);
        return root;
    }

    // binary tree traversal function
    void traverse(TreeNode* root) {
        if(root != NULL) {
            // *** pre-order position ***
            // what each node needs to do is to swap its left and right child nodes
            TreeNode* tmp = root->left;
            root->left = root->right;
            root->right = tmp;

            // traversal framework, go and traverse the nodes of the left and right subtrees
            traverse(root->left);
            traverse(root->right);
        }
    }
};

python 🤖

class Solution:
    # main function
    def invertTree(self, root):
        # traverse the binary tree, swap the children of each node
        self.traverse(root)
        return root

    # binary tree traversal function
    def traverse(self, root):
        if not root:
            return 
        
        # *** pre-order position ***
        # what each node needs to do is swap its left and right children
        tmp = root.left
        root.left = root.right
        root.right = tmp

        # traversal framework, go traverse the nodes of the left and right subtrees
        self.traverse(root.left)
        self.traverse(root.right)

go 🤖

// main function
func invertTree(root *TreeNode) *TreeNode {
    // traverse the binary tree, swap the child nodes of each node
    traverse(root)
    return root
}

// binary tree traversal function
func traverse(root *TreeNode) {
    if root == nil {
        return
    }

    // *** preorder position ***
    // what each node needs to do is swap its left and right children
    tmp := root.Left
    root.Left = root.Right
    root.Right = tmp

    // traversal framework, go and traverse the nodes of the left and right subtrees
    traverse(root.Left)
    traverse(root.Right)
}

javascript 🤖

// main function
var invertTree = function(root) {
    traverse(root);
    return root;
};

// binary tree traversal function
function traverse(root) {
    if (root == null) {
        return;
    }

    // *** preorder position ***
    // what each node needs to do is swap its left and right children
    let tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // traversal framework, go and traverse the nodes of the left and right subtrees
    traverse(root.left);
    traverse(root.right);
}

You can move the code from the pre-order position to the post-order position, but directly moving it to the in-order position won't work; it needs a slight modification. This should be quite obvious, so I won't elaborate on it.

Technically, we've solved this problem, but for comparison, let's continue thinking.

2. Can this problem be solved using the "divide and conquer" approach?

Let's try to define the invertTree function:

java 🟢

// Define: invert the binary tree with root, and return the root node of the inverted binary tree
TreeNode invertTree(TreeNode root);

cpp 🤖

// Define: invert the binary tree with root, return the root node of the inverted binary tree
TreeNode* invertTree(TreeNode* root);

python 🤖

# Definition: Invert the binary tree rooted at 'root', return the root node of the inverted tree
def invertTree(root: TreeNode)

go 🤖

// Definition: Invert the binary tree rooted at 'root', return the root node of the inverted tree
func invertTree(root *TreeNode) *TreeNode

javascript 🤖

// Definition: Invert the binary tree rooted at 'root', return the root node of the inverted tree
var invertTree = function(root) {}

Then think about it, when you execute invertTree(x) for a certain binary tree node x, what can you do using the definition of this recursive function?

I can use invertTree(x.left) to first invert the left subtree of x, then use invertTree(x.right) to invert the right subtree of x. Finally, I swap the left and right subtrees of x. This exactly completes the inversion of the entire binary tree rooted at x, thus fulfilling the definition of invertTree(x).

Here is the solution code directly:

java 🟢

class Solution {
    // Definition: Invert the binary tree rooted at 'root', return the root node of the inverted tree
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        // Utilize the function definition to invert left and right subtrees first
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        // Then swap the left and right child nodes
        root.left = right;
        root.right = left;

        // Consistent with the definition logic: the binary tree rooted at 'root' has been inverted, return root
        return root;
    }
}

cpp 🤖

class Solution {
public:
    // Definition: Invert the binary tree rooted at 'root', return the root node of the inverted tree
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        // Utilize the function definition to invert the left and right subtrees first
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);

        // Then swap the left and right child nodes
        root->left = right;
        root->right = left;

        // Consistent with the definition logic: the binary tree rooted at 'root' has been inverted, return root
        return root;
    }
};

python 🤖

class Solution:
    # Definition: Invert the binary tree rooted at 'root', return the root node of the inverted tree
    def invertTree(self, root):
        if root is None:
            return None
        # Utilize the function definition to invert left and right subtrees first
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)

        # Then swap the left and right child nodes
        root.left, root.right = right, left

        # Consistent with the definition logic: the tree rooted at 'root' has been inverted, return root
        return root

go 🤖

// Definition: Invert the binary tree rooted at 'root', return the root node of the inverted tree
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    // Use the function definition to invert the left and right subtrees first
    left := invertTree(root.Left)
    right := invertTree(root.Right)

    // Then swap the left and right child nodes
    root.Left = right
    root.Right = left

    // Consistent with the definition logic: the binary tree rooted at 'root' has been inverted, return root
    return root
}

javascript 🤖

// Definition: Invert the binary tree rooted at 'root', and return the root node of the inverted tree
var invertTree = function(root) {
    if (root == null) {
        return null;
    }
    // Utilize the function definition to invert left and right subtrees first
    var left = invertTree(root.left);
    var right = invertTree(root.right);

    // Then swap the left and right child nodes
    root.left = right;
    root.right = left;

    // Consistent with the definition logic: the binary tree rooted at 'root' has been inverted, return root
    return root;
}

The core of this "break down the problem" approach is to give the recursive function a suitable definition and then use that definition to explain your code. If your logic is self-consistent, then your algorithm is correct.

Alright, that's the analysis for this problem. Both the "traversal" and "break down the problem" approaches can solve it. Let's move on to the next problem.

Second Problem: Populating Next Right Pointers in Each Node

This is LeetCode problem #116, "Populating Next Right Pointers in Each Node." Let's look at the problem statement:

116. Populating Next Right Pointers in Each Node | 力扣 | LeetCode |

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 212 - 1].
• -1000 <= Node.val <= 1000

Follow-up:

• You may only use constant extra space.
• The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

java 🟢

// Function signature
Node connect(Node root);

cpp 🤖

// Function signature
Node* connect(Node* root);

python 🤖

# Function signature
def connect(root: 'Node')

go 🤖

// Function signature
func connect(root *Node) *Node

javascript 🤖

// Function signature
var connect = function(root) {}

The problem requires connecting all nodes at each level of a binary tree using next pointers:

The input is a "perfect binary tree," which means the entire tree forms a perfect triangle. Except for the rightmost node, whose next pointer points to null, every other node has a neighboring node to its right.

How do we solve this problem? Let's recall the general approach to binary tree problems:

1. Can this problem be solved using a "traversal" mindset?

Clearly, it can.

The task for each node is simple: point its next pointer to the node on its right.

You might try to模仿 the previous problem and write the following code directly:

java 🟢

// Binary tree traversal function
void traverse(Node root) {
    if (root == null || root.left == null) {
        return;
    }
    // Point the next pointer of the left child to the right child
    root.left.next = root.right;

    traverse(root.left);
    traverse(root.right);
}

cpp 🤖

// Binary tree traversal function
void traverse(TreeNode* root) {
    if (root == NULL || root->left == NULL) {
        return;
    }
    // Point the next pointer of the left child to the right child
    root->left->next = root->right;

    traverse(root->left);
    traverse(root->right);
}

python 🤖

# Binary tree traversal function
def traverse(root):
    if root is None or root.left is None:
        return
    # Point the next pointer of the left child to the right child
    root.left.next = root.right

    traverse(root.left)
    traverse(root.right)

go 🤖

// Binary tree traversal function
func traverse(root *Node) {
    if root == nil || root.Left == nil {
        return
    }
    // Point the Next pointer of the left child to the right child
    root.Left.Next = root.Right

    traverse(root.Left)
    traverse(root.Right)
}

javascript 🤖

// Binary tree traversal function
var traverse = function(root) {
    if (root == null || root.left == null) {
        return;
    }
    // Point the next pointer of the left child to the right child
    root.left.next = root.right;

    traverse(root.left);
    traverse(root.right);
}

However, this code actually has a significant issue because it can only connect two nodes with the same parent. Take a look at this diagram:

Nodes 5 and 6 do not share the same parent. According to the logic of this code, they cannot be connected, which does not meet the requirements of the problem. But where is the issue?

The traditional traverse function visits all nodes of a binary tree, but what we want to traverse now are the "gaps" between two adjacent nodes.

Therefore, we can abstract the binary tree. Consider each box in the diagram as a node:

This way, a binary tree is abstracted into a ternary tree, where each node in the ternary tree represents two adjacent nodes in the original binary tree.

Now, we just need to implement a traverse function to traverse this ternary tree. The task for each "ternary tree node" is to connect its two internal binary tree nodes:

java 🟢

class Solution {
    // Main function
    public Node connect(Node root) {
        if (root == null) return null;
        // Traverse the "ternary tree" and connect adjacent nodes
        traverse(root.left, root.right);
        return root;
    }

    // Ternary tree traversal framework
    void traverse(Node node1, Node node2) {
        if (node1 == null || node2 == null) {
            return;
        }
        // *** Pre-order position ***
        // Connect the two input nodes
        node1.next = node2;
        
        // Connect two child nodes with the same parent
        traverse(node1.left, node1.right);
        traverse(node2.left, node2.right);
        // Connect two child nodes across parent nodes
        traverse(node1.right, node2.left);
    }
}

cpp 🤖

class Solution {
public:
    // Main function
    Node* connect(Node* root) {
        if (root == nullptr) return nullptr;
        // Traverse the "ternary tree" and connect adjacent nodes
        traverse(root->left, root->right);
        return root;
    }

    // Ternary tree traversal framework
    void traverse(Node* node1, Node* node2) {
        if (node1 == nullptr || node2 == nullptr) {
            return;
        }
        // *** Pre-order position ***
        // Connect the two input nodes
        node1->next = node2;
        
        // Connect two child nodes with the same parent
        traverse(node1->left, node1->right);
        traverse(node2->left, node2->right);
        // Connect two child nodes across different parents
        traverse(node1->right, node2->left);
    }
};

python 🤖

class Solution:
    # Main function
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        # Traverse the "ternary tree" and connect adjacent nodes
        self.traverse(root.left, root.right)
        return root

    # Ternary tree traversal framework
    def traverse(self, node1: 'Node', node2: 'Node') -> None:
        if not node1 or not node2:
            return
        # Pre-order position
        # Connect the two input nodes
        node1.next = node2 
        
        # Connect two child nodes with the same parent
        self.traverse(node1.left, node1.right)
        self.traverse(node2.left, node2.right)
        # Connect two child nodes across different parents
        self.traverse(node1.right, node2.left)

go 🤖

// Main function
func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    // Traverse the "ternary tree" and connect adjacent nodes
    traverse(root.Left, root.Right)
    return root
}

// Ternary tree traversal framework
func traverse(node1 *Node, node2 *Node) {
    if node1 == nil || node2 == nil {
        return
    }

    // *** Pre-order position ***
    // Connect the two input nodes
    node1.Next = node2
    
    // Connect two child nodes with the same parent
    traverse(node1.Left, node1.Right)
    traverse(node2.Left, node2.Right)
    // Connect two child nodes across different parents
    traverse(node1.Right, node2.Left)
}

javascript 🤖

var connect = function(root) {
    // main function
    if (root == null) return null;
    // traverse the "ternary tree" and connect adjacent nodes
    traverse(root.left, root.right);
    return root;

    // ternary tree traversal framework
    function traverse(node1, node2) {
        if (node1 == null || node2 == null) {
            return;
        }
        // *** pre-order position ***
        // connect the two input nodes
        node1.next = node2;
        
        // connect two child nodes of the same parent
        traverse(node1.left, node1.right);
        traverse(node2.left, node2.right);
        // connect two child nodes across different parents
        traverse(node1.right, node2.left);
    }
};

This way, the traverse function traverses the entire "ternary tree," connecting all adjacent binary tree nodes, thus avoiding the issues we encountered earlier and perfectly solving this problem.

2. Can this problem be solved using the "break down the problem" thinking pattern?

Well, it seems there isn't a particularly good approach, so this problem cannot be solved using the "break down the problem" thinking pattern.

Third Problem: Flatten Binary Tree to Linked List

This is LeetCode problem #114 "Flatten Binary Tree to Linked List." Let's look at the problem statement:

114. Flatten Binary Tree to Linked List | 力扣 | LeetCode |

Given the root of a binary tree, flatten the tree into a "linked list":

• The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

java 🟢

// The function signature is as follows
void flatten(TreeNode root);

for (int i = n - 2; i >= 0; i--)
    r_max[i] = Math.max(height[i], r_max[i + 1]);

for (int i = 1; i < n - 1; i++) {
    // hello world
    res += Math.min(l_max[i], r_max[i]) - height[i];

}

cpp 🤖

// The function signature is as follows
void flatten(TreeNode* root);

python 🤖

# The function signature is as follows
def flatten(root: TreeNode)

go 🤖

// The function signature is as follows
func flatten(root *TreeNode)

javascript 🤖

// The function signature is as follows
var flatten = function(root) {}

1、这题能不能用「遍历」的思维模式解决？

乍一看感觉是可以的：对整棵树进行前序遍历，一边遍历一边构造出一条「链表」就行了：

java 🟢

// Virtual head node, dummy.right is the result
TreeNode dummy = new TreeNode(-1);
// Pointer used to build the linked list
TreeNode p = dummy;

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // Pre-order position
    p.right = new TreeNode(root.val);
    p = p.right;

    traverse(root.left);
    traverse(root.right);
}

cpp 🤖

// Virtual head node, dummy.right is the result
TreeNode* dummy = new TreeNode(-1);
// Pointer used to build the linked list
TreeNode* p = dummy;

void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // Pre-order position
    p->right = new TreeNode(root->val);
    p = p->right;

    traverse(root->left);
    traverse(root->right);
}

python 🤖

# Virtual head node, dummy.right is the result
dummy = TreeNode(-1)
# Pointer used to build the linked list
p = dummy

def traverse(root: TreeNode):
    if root is None:
        return
    # Pre-order position
    p.right = TreeNode(root.val)
    p = p.right

    traverse(root.left)
    traverse(root.right)

go 🤖

var p *TreeNode

// Virtual head node, dummy.right is the result
var dummy = newTreeNode(-1)
p = dummy

func traverse(root *TreeNode) {
	if root == nil {
		return
	}
	// Pre-order position
	p.Right = &TreeNode{Val: root.Val}
	p = p.Right

	traverse(root.Left)
	traverse(root.Right)
}

javascript 🤖

// Virtual head node, dummy.right is the result
var dummy = new TreeNode(-1);
// Pointer used to build the linked list
var p = dummy;

var traverse = function(root) {
    if (root == null) {
        return;
    }
    // Pre-order position
    p.right = new TreeNode(root.val);
    p = p.right;

    traverse(root.left);
    traverse(root.right);
}

However, pay attention to the signature of the flatten function, which returns void. This means the problem expects us to flatten the binary tree into a linked list in place.

With this requirement, we cannot solve the problem through simple binary tree traversal.

2. Can this problem be solved using the "divide and conquer" thinking pattern?

Let's try to define the flatten function:

java 🟢

// Definition: Input node root, then the binary tree rooted at root will be flattened into a linked list
void flatten(TreeNode root);

cpp 🤖

// Definition: Input node root, then the binary tree rooted at root will be flattened into a linked list
void flatten(TreeNode* root);

python 🤖

# Definition: Input node root, then the binary tree with root as the root will be flattened into a linked list
def flatten(self, root: TreeNode) -> None:

go 🤖

// Definition: Input node root, then the binary tree with root as the root will be flattened into a linked list
func flatten(root *TreeNode) {
}

javascript 🤖

// Definition: Input node root, then the binary tree with root as the root will be flattened into a linked list
var flatten = function(root) {

};

With this function definition, how do you flatten a binary tree into a linked list as required by the problem?

For a node x, you can follow these steps:

1. First, use flatten(x.left) and flatten(x.right) to flatten x's left and right subtrees.

2. Attach x's right subtree to the bottom of the left subtree, then make the entire left subtree the new right subtree.

This way, the entire binary tree rooted at x is flattened, which perfectly fits the definition of flatten(x).

Here is the direct code implementation:

java 🟢

class Solution {
    // Definition: flatten the tree with root as the root node into a linked list
    public void flatten(TreeNode root) {
        // base case
        if (root == null) return;
        
        // Utilize the definition to flatten the left and right subtrees
        flatten(root.left);
        flatten(root.right);

        // *** Post-order traversal position ***
        // 1. Left and right subtrees have been flattened into linked lists
        TreeNode left = root.left;
        TreeNode right = root.right;
        
        // 2. Make the left subtree the new right subtree
        root.left = null;
        root.right = left;

        // 3. Attach the original right subtree to the end of the current right subtree
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;

    }
}

cpp 🤖

class Solution {
public:
    // Definition: flatten the tree rooted at 'root' into a linked list
    void flatten(TreeNode* root) {
        // base case
        if (root == nullptr) return;

        // Use the definition to flatten the left and right subtrees
        flatten(root->left);
        flatten(root->right);

        // *** Post-order traversal position ***
        // 1. Left and right subtrees have been flattened into linked lists
        TreeNode* left = root->left;
        TreeNode* right = root->right;

        // 2. Make the left subtree the new right subtree
        root->left = nullptr;
        root->right = left;

        // 3. Attach the original right subtree to the end of the current right subtree
        TreeNode* p = root;
        while (p->right != nullptr) {
            p = p->right;
        }
        p->right = right;

    }
};

python 🤖

class Solution:
    # Definition: flatten the tree rooted at 'root' into a linked list
    def flatten(self, root) -> None:
        # base case
        if root is None:
            return

        # Use the definition to flatten left and right subtrees
        self.flatten(root.left)
        self.flatten(root.right)

        # Post-order traversal position
        # 1. Left and right subtrees have been flattened into linked lists
        left = root.left
        right = root.right

        # 2. Make the left subtree the new right subtree
        root.left = None
        root.right = left

        # 3. Attach the original right subtree to the end of the current right subtree
        p = root
        while p.right is not None:
            p = p.right
        p.right = right 

go 🤖

// Definition: flatten the tree with root as the root into a linked list
func flatten(root *TreeNode) {
    // base case
    if root == nil {
        return
    }
    
    // Using the definition, flatten the left and right subtrees
    flatten(root.Left)
    flatten(root.Right)

    // *** Post-order traversal position ***
    // 1. Left and right subtrees have been flattened into a linked list
    left := root.Left
    right := root.Right
       
    // 2. Make the left subtree the right subtree
    root.Left = nil
    root.Right = left

    // 3. Attach the original right subtree to the end of the current right subtree
    p := root
    for p.Right != nil {
        p = p.Right
    }
    p.Right = right

}

javascript 🤖

var flatten = function(root) {
    // Definition: flatten the tree with root as the root into a linked list
    // base case
    if (root == null) return;

    // Utilize the definition to flatten the left and right subtrees
    flatten(root.left);
    flatten(root.right);

    // *** Post-order traversal position ***
    // 1. Left and right subtrees have been flattened into a linked list
    var left = root.left;
    var right = root.right;

    // 2. Make the left subtree the right subtree
    root.left = null;
    root.right = left;

    // 3. Attach the original right subtree to the end of the current right subtree
    var p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;

};

See, this is the charm of recursion. How does the flatten function manage to flatten the left and right subtrees?

It's not easy to explain, but as long as you understand the definition of flatten and use this definition, letting each node do its job, the flatten function will work as defined.

With this, the problem is solved. The recursive approach in our previous article Flipping a Linked List in Groups of k is somewhat similar to this problem.

Finally, to tie it all together, let's recite the general guidelines for solving binary tree problems once more.

The thought process for solving binary tree problems can be divided into two categories:

1. Can the answer be obtained by traversing the binary tree once? If so, use a traverse function along with external variables to achieve this. This is the "traversal" thought pattern.

2. Can a recursive function be defined that derives the answer to the original problem from the answers to subproblems (subtrees)? If so, write the definition of this recursive function and make full use of its return value. This is the "problem decomposition" thought pattern.

Regardless of which thought pattern you use, you need to consider:

What does a single binary tree node need to do? When does it need to do it (pre-order, in-order, or post-order position)? You don't need to worry about other nodes; the recursive function will execute the same operation on all nodes for you.

I hope you can carefully understand and apply this to all binary tree problems.

This article ends here. For more classic binary tree exercises and training in recursive thinking, please refer to the Recursive Special Practice section in the binary tree chapter.

---

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode	力扣
-	剑指 Offer 26. 树的子结构
-	剑指 Offer 27. 二叉树的镜像

---