二叉树找两结点之间的路径，采用什么遍历方法

在二叉树中找到两个结点之间的路径，可以使用任何一种遍历方法，包括前序遍历、中序遍历和后序遍历，但最常用的方法是采用深度优先搜索算法中的前序遍历。

具体实现方法是，首先从根节点开始遍历整棵树，同时记录下遍历过程中的路径，当遇到第一个要查找的节点时，就把当前路径保存下来。接着继续遍历整棵树，当遇到第二个要查找的节点时，就把当前路径和之前保存下来的路径合并起来，即为所求的两个节点之间的路径。

这种方法的时间复杂度为O(n)，其中n为树中节点的个数。

相关问题

求二叉树中从根结点到叶子结点的路径；采用先序遍历输出所有从叶子结点到根结点的逆路径，并输出第一条最长的逆路径，采用后序非递归遍历输出所有从叶子结点到根结点的逆路径，采用层次遍历方法输出所有从叶子结点到根结点的逆路径

二叉树中从根结点到叶子结点的路径可以采用深度优先遍历（DFS）中的前序遍历（先访问根节点，再访问左子树和右子树）实现，当遍历到叶子节点时，将路径加入结果中。具体实现可以参考以下代码：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def findPaths(root):
    res = [] # 存储所有路径

    def dfs(node, path):
        if not node:
            return
        if not node.left and not node.right: # 叶子节点
            res.append(path + [node.val])
            return
        dfs(node.left, path + [node.val])
        dfs(node.right, path + [node.val])

    dfs(root, [])
    return res

采用先序遍历输出所有从叶子结点到根结点的逆路径，并输出第一条最长的逆路径，可以修改上述代码，在遍历到叶子节点时，将路径逆序后加入结果中。同时记录路径长度，找到最长的路径。具体实现可以参考以下代码：

def findPaths(root):
    res = [] # 存储所有路径
    longest_path = [] # 存储最长的逆路径
    max_length = 0 # 最长逆路径的长度

    def dfs(node, path):
        if not node:
            return
        if not node.left and not node.right: # 叶子节点
            rev_path = path + [node.val]
            rev_path.reverse()
            res.append(rev_path)
            if len(rev_path) > max_length:
                max_length = len(rev_path)
                longest_path[:] = rev_path # 注意要使用切片复制

        dfs(node.left, path + [node.val])
        dfs(node.right, path + [node.val])

    dfs(root, [])
    return res, longest_path

采用后序非递归遍历输出所有从叶子结点到根结点的逆路径可以使用栈来实现。具体思路是，先用后序遍历遍历整棵树，同时在遍历的过程中记录当前路径。当遍历到叶子节点时，将路径逆序后压入栈中。遍历完整棵树后，弹出栈中的元素，即可得到所有从叶子节点到根节点的逆路径。具体实现可以参考以下代码：

def postorderTraversal(root):
    res = []
    stack = []
    prev = None
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack[-1]
        if not root.right or root.right == prev:
            stack.pop()
            res.append(root)
            prev = root
            root = None
        else:
            root = root.right
    return res

def findPaths(root):
    res = [] # 存储所有路径
    stack = [] # 存储从叶子节点到根节点的逆路径

    def reversePath(path):
        rev_path = path[:]
        rev_path.reverse()
        return rev_path

    for node in postorderTraversal(root):
        if not node.left and not node.right: # 叶子节点
            stack.append(node)
        else:
            while stack and stack[-1].val not in (node.left.val, node.right.val):
                stack.pop()
            if stack:
                path = [n.val for n in stack]
                path.append(node.val)
                res.append(reversePath(path))
            stack.append(node)

    return res

采用层次遍历方法输出所有从叶子结点到根结点的逆路径可以利用队列和字典来实现。具体思路是，先用层次遍历遍历整棵树，同时在遍历的过程中记录每个节点的父节点。当遍历到叶子节点时，利用字典回溯到根节点，即可得到从叶子节点到根节点的逆路径。具体实现可以参考以下代码：

def findPaths(root):
    res = [] # 存储所有路径
    queue = [(root, None)] # 存储节点和其父节点的元组
    parent = {} # 存储每个节点的父节点

    while queue:
        node, p = queue.pop(0)
        if not node.left and not node.right: # 叶子节点
            path = [node.val]
            while node:
                path.append(node.val)
                node = parent.get(node)
            res.append(path[:-1][::-1])
        if node.left:
            parent[node.left] = node
            queue.append((node.left, node))
        if node.right:
            parent[node.right] = node
            queue.append((node.right, node))

    return res

编写非递归遍历算法，C语言实现:给定一棵二叉树的先序遍历序列和中序遍历序列，创建这棵二叉树 1输出二叉树的后序遍历的结点序列 2输出二叉树的叶子结点 3统计二叉树的结点个数 4求二叉树的深度 5输出二叉树指定结点的路径

以下是非递归遍历算法的C语言实现，包括先序遍历、中序遍历和后序遍历：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结点
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 定义栈结构体
typedef struct Stack {
    int top;
    int size;
    TreeNode** data;
} Stack;

// 初始化栈
Stack* initStack(int size) {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    s->top = -1;
    s->size = size;
    s->data = (TreeNode**)malloc(sizeof(TreeNode*) * size);
    return s;
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}

// 入栈
void push(Stack* s, TreeNode* t) {
    if (s->top == s->size - 1) return;
    s->data[++(s->top)] = t;
}

// 出栈
TreeNode* pop(Stack* s) {
    if (isEmpty(s)) return NULL;
    return s->data[(s->top)--];
}

// 非递归先序遍历
void preOrder(TreeNode* root) {
    if (!root) return;
    Stack* s = initStack(100);
    push(s, root);
    while (!isEmpty(s)) {
        TreeNode* t = pop(s);
        printf("%d ", t->val);
        if (t->right) push(s, t->right);
        if (t->left) push(s, t->left);
    }
}

// 非递归中序遍历
void inOrder(TreeNode* root) {
    if (!root) return;
    Stack* s = initStack(100);
    TreeNode* t = root;
    while (!isEmpty(s) || t) {
        if (t) {
            push(s, t);
            t = t->left;
        } else {
            t = pop(s);
            printf("%d ", t->val);
            t = t->right;
        }
    }
}

// 非递归后序遍历
void postOrder(TreeNode* root) {
    if (!root) return;
    Stack* s1 = initStack(100);
    Stack* s2 = initStack(100);
    push(s1, root);
    while (!isEmpty(s1)) {
        TreeNode* t = pop(s1);
        push(s2, t);
        if (t->left) push(s1, t->left);
        if (t->right) push(s1, t->right);
    }
    while (!isEmpty(s2)) {
        TreeNode* t = pop(s2);
        printf("%d ", t->val);
    }
}

接下来是创建二叉树、输出叶子结点、统计结点个数、求深度和输出指定结点路径等功能的实现：

// 根据先序遍历序列和中序遍历序列创建二叉树
TreeNode* buildTree(int* preorder, int preStart, int preEnd, int* inorder, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) return NULL;
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = preorder[preStart];
    int i;
    for (i = inStart; i <= inEnd; i++) {
        if (inorder[i] == root->val) break;
    }
    int leftLen = i - inStart;
    root->left = buildTree(preorder, preStart + 1, preStart + leftLen, inorder, inStart, i - 1);
    root->right = buildTree(preorder, preStart + leftLen + 1, preEnd, inorder, i + 1, inEnd);
    return root;
}

// 输出二叉树的叶子结点
void printLeaves(TreeNode* root) {
    if (!root) return;
    if (!root->left && !root->right) printf("%d ", root->val);
    printLeaves(root->left);
    printLeaves(root->right);
}

// 统计二叉树的结点个数
int countNodes(TreeNode* root) {
    if (!root) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// 求二叉树的深度
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

// 输出二叉树指定结点的路径
int findPath(TreeNode* root, int val, int* path, int index) {
    if (!root) return 0;
    path[index++] = root->val;
    if (root->val == val) return 1;
    if (findPath(root->left, val, path, index) || findPath(root->right, val, path, index)) {
        return 1;
    }
    return 0;
}

以上就是给定先序遍历序列和中序遍历序列创建二叉树，并实现一些二叉树操作的C语言代码。