代码天涯路

144. 二叉树的前序遍历(Binary Tree Preorder Traversal)E

英文题目

  • Given the root of a binary tree, return the preorder traversal of its nodes' values.

  • Example 1:

  • Input: root = [1,null,2,3]
Output: [1,2,3]

  • Example 2:

  • Input: root = []
Output: []

  • Example 3:

  • Input: root = [1]
Output: [1]

  • Example 4:

  • Input: root = [1,2]
Output: [1,2]

  • Example 5:

  • Input: root = [1,null,2]
Output: [1,2]

  • Constraints:

  • The number of nodes in the tree is in the range [0, 100].

  • -100 <= Node.val <= 100

  • Follow up:

  • Recursive solution is trivial, could you do it iteratively?

中文题目

  • 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

  • 示例 1：

  • 输入：root = [1,null,2,3]
输出：[1,2,3]

  • 示例 2：

  • 输入：root = []
输出：[]

  • 示例 3：

  • 输入：root = [1]
输出：[1]

  • 示例 4：

  • 输入：root = [1,2]
输出：[1,2]

  • 示例 5：

  • 输入：root = [1,null,2]
输出：[1,2]

  • 提示：

  • 树中节点数目在范围 [0, 100] 内

  • -100 <= Node.val <= 100

  • 进阶：递归算法很简单，你可以通过迭代算法完成吗？

递归

  • 按照访问根节点-左子树-右子树的顺序遍历

  • 时间复杂度O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次

  • 空间复杂度O(n)，为递归过程中栈的开销，平均情况下为 O(log⁡ n)，最坏情况下树呈现链状，为 O(n)

    # python3: 时间 40 ms, 击败 66.00%; 内存 15.64 MB, 击败 43.47%
# 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
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        self.res = []
        self.dfs(root)
        return self.res
    
    def dfs(self, root: Optional[TreeNode]) -> None:
        if not root:
            return
        self.res.append(root.val)
        self.dfs(root.left)
        self.dfs(root.right)
        

    // c++: 时间 4 ms, 击败 41.96%; 内存 8.2 MB, 击败 33.54%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        dfs(res, root);
        return res;
    }

    void dfs(vector<int> &res, TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val);
        dfs(res, root->left);
        dfs(res, root->right);
    }
};

    // java: 时间 4 ms, 击败 41.96%; 内存 8.2 MB, 击败 33.54%
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(res, root);
        return res;
    }

    public void dfs(List<Integer> res, TreeNode root) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        dfs(res, root.left);
        dfs(res, root.right);
    }
}

    // go: 时间 0 ms, 击败 100%; 内存 1.83 MB, 击败 99.95%
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    dfs(&res, root)
    return res
}

// 特别注意结果数组需要传递引用
func dfs(res *[]int, root *TreeNode) {
    if root == nil {
        return
    }
    *res = append(*res, root.Val)
    dfs(res, root.Left)
    dfs(res, root.Right)
}

    // javascript: 时间 68 ms, 击败 24.6%; 内存 41.1 MB, 击败 59.97%
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let res = [];
    dfs(res, root);
    return res;
};

const dfs = function(res, root) {
    if (root == null) {
        return;
    }
    res.push(root.val);
    dfs(res, root.left);
    dfs(res, root.right);
}

迭代

  • 使用栈，初始把根节点入栈

  • 当栈不为空时，把栈顶元素，即根节点值加入到结果中，然后先入栈右子树，再入栈左子树

  • 时间复杂度O(n)，空间复杂度O(n)

    # python3: 时间 40 ms, 击败 66%; 内存 16.1 MB, 击败 21.79%
# 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
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if not root:
            return res
        # 初始化栈，并将根节点入栈
        stack = [root]
        while stack:
            node = stack.pop()
            # 当栈不为空时，把栈顶元素，即根节点值加入到结果中
            res.append(node.val)
            # 如果 node 的右子树非空，将右子树入栈
            if node.right:
                stack.append(node.right)
            # 如果 node 的左子树非空，将左子树入栈
            if node.left:
                stack.append(node.left)
        return res

    // c++: 时间 0 ms, 击败 100%; 内存 8.1 MB, 击败 84.85%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            res.push_back(node->val);
            if (node->right != nullptr) {
                st.push(node->right);
            }
            if (node->left != nullptr) {
                st.push(node->left);
            }
        }
        return res;
    }
};

    // java: 时间 0 ms, 击败 100%; 内存 39.6 MB, 击败 75.75%
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            stack.pop();
            res.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return res;
    }
}

    // go: 时间 0 ms, 击败 100%; 内存 39.6 MB, 击败 75.75%
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }
    return res
}

    // javascript: 
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let res = [];
    if (root == null) {
        return res;
    }
    const stack = [root];
    while (stack.length) {
        node = stack.pop();
        res.push(node.val);
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    return res;
};

Morris遍历

  • 参考：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/656142/cer-cha-shu-san-chong-bian-li-qian-zhong-erk2/

  • 整体思路是，先建立根节点在中序遍历下的前驱节点和自身的连接，即上图 1 到 图 2，然后即可顺着上述连接遍历，返回根节点时，再断开连接

  • 分为4 步：

    • 1.从根节点开始，找到根节点在中序遍历下的前驱节点，建立连接(由上至下)，向左子树前进
    • 2.左侧到头时，向右子树前进(由下至上)，因此时右子树指向的是根节点，则回到了根节点
    • 3.由根节点再找一遍该根节点在中序遍历下的前驱节点，断开连接
    • 4.向右子树前进

  • 时间复杂度O(n)，空间复杂度O(1)

    # python: 时间 44 ms, 击败 41.96%; 内存 15.9 MB, 击败 62.46%
# 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
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if not root:
            return res
        cur = root
        while cur:
            curLeft = cur.left
            
            # 当左子树存在，即可建立前驱节点的连接
            if curLeft:
                while curLeft.right and curLeft.right != cur:
                    # 此时curLeft是cur节点中序遍历的前驱节点
                    curLeft = curLeft.right

                if not curLeft.right:
                    # 1.第一次是找前驱节点，并建立连接
                    curLeft.right = cur
                    # 这里输出的是有左子树的根节点
                    res.append(cur.val)
                    cur = cur.left # 2.不断向左子树前进
                    continue # 注意，先建立完所有左子树的连接
                else:
                    # 3.此时是已返回了上层节点，再次找到前驱节点
                    # 断开连接
                    curLeft.right = None
            else:
                # 当前节点无左子树，则可直接输出当前节点
                res.append(cur.val)
            
            # 2、4.左子树到头了，向右子树前进，有两种可能：
            # 可能是树本身的右子树，也可能是在上面建立起来的到根节点连接
            cur = cur.right
        return res

    // c++: 时间 0 ms, 击败 100%; 内存 8.1 MB, 击败 78.71%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        TreeNode * cur = root;
        while (cur != nullptr) {
            TreeNode * curLeft = cur->left;
            if (curLeft != nullptr) {
                while (curLeft->right != nullptr && curLeft->right != cur) {
                    curLeft = curLeft->right;
                }
                if (curLeft->right == nullptr) {
                    curLeft->right = cur;
                    res.push_back(cur->val);
                    cur = cur->left;
                    continue;
                } else {
                    curLeft->right = nullptr;
                }
            } else {
                res.push_back(cur->val);
            }
            cur = cur->right;
        }
        return res;
    }
};

    // java: 时间 0 ms, 击败 100%; 内存 39.6 MB, 击败 85.13%
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        TreeNode cur = root;
        while (cur != null) {
            TreeNode curLeft = cur.left;
            if (curLeft != null) {
                while (curLeft.right != null && curLeft.right != cur) {
                    curLeft = curLeft.right;
                }
                if (curLeft.right == null) {
                    curLeft.right = cur;
                    res.add(cur.val);
                    cur = cur.left;
                    continue;
                } else {
                    curLeft.right = null;
                }
            } else {
                res.add(cur.val);
            }
            cur = cur.right;
        }
        return res;
    }
}

    // go: 时间 0 ms, 击败 100%; 内存 1.9 MB, 击败 80.46%
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }
    cur := root
    for cur != nil {
        curLeft := cur.Left
        if curLeft != nil {
            for curLeft.Right != nil && curLeft.Right != cur {
                curLeft = curLeft.Right
            }
            if curLeft.Right == nil {
                curLeft.Right = cur
                res = append(res, cur.Val)
                cur = cur.Left
                continue
            } else {
                curLeft.Right = nil
            }
        } else {
            res = append(res, cur.Val)
        }
        cur = cur.Right
    }
    return res
}

    // javascript: 时间 60 ms, 击败 69.63%; 内存 41 MB, 击败 78.55%
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let res = [];
    if (root == null) {
        return res;
    }
    let cur = root;
    while (cur != null) {
        let curLeft = cur.left;
        if (curLeft != null) {
            while (curLeft.right != null && curLeft.right != cur) {
                curLeft = curLeft.right;
            }
            if (curLeft.right == null) {
                curLeft.right = cur;
                res.push(cur.val);
                cur = cur.left;
                continue;
            } else {
                curLeft.right = null;
            }
        } else {
            res.push(cur.val);
        }
        cur = cur.right;
    }
    return res;
};
Last Updated:
Contributors: Shiqi Lu