Leetcode-144、二叉树的前序遍历

一、题目

二、题解

递归

Java题解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        _preorder(root, res);
        return res;
    }
    private void _preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        _preorder(root.left, res);
        _preorder(root.right, res);
    }
}

结果

image.png

Python解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

结果

image.png

迭代

Java题解1

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode p = root;
        Stack<TreeNode> stack = new Stack<>();
        while (p != null || stack.size() != 0) {
            if (p != null) {
                stack.push(p);
                res.add(p.val);
                p = p.left;
            } else {
                TreeNode tmp = stack.pop();
                p = tmp.right;
            }
        }
        return res;
    }
}

结果

image.png

迭代本质上是模拟递归，因为递归过程中用了系统栈，所以迭代法中常用stack模拟系统栈。

前序遍历：根-左-右
步骤：
1、先将头节点放入stack，然后打印或保存到res中
2、stack中先放入右子树，再放入左子树，打印时就先打印左子树，再打印右子树

image.png

Java题解2

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.pop();
            res.add(tmp.val);
            if (tmp.right != null) {
                stack.push(tmp.right);
            }
            if (tmp.left != null) {
                stack.push(tmp.left);
            }
        }
        return res;
    }
}

Java题解3
英文版上面看到的高分解

public List<Integer> preorderTraversal(TreeNode node) {
    List<Integer> list = new LinkedList<Integer>();
    Stack<TreeNode> rights = new Stack<TreeNode>();
    while(node != null) {
        list.add(node.val);
        if (node.right != null) {
            rights.push(node.right);
        }
        node = node.left;
        if (node == null && !rights.isEmpty()) {
            node = rights.pop();
        }
    }
    return list;
}

Java题解4
题解2的基础上，空节点也入栈

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode top = stack.pop();
            if (top != null) {
                res.add(top.val);
                stack.push(top.right);
                stack.push(top.left);
            }
        }
        return res;
    }
}

Python题解1

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res, stack = [], [root]
        # res = []
        # stack = [root]
        if not root:
            return res;
        # while len(stack) > 0:
        while stack:      #
            top = stack.pop()
            res.append(top.val)
            # if top.right != None:
            if top.right:
                stack.append(top.right)
            # if top.left != None:
            if top.left:
                stack.append(top.left)
        return res

Python题解2
空节点也入栈，只是在放入结果list时判断是否为空

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