美文网首页
栈-N144-二叉树的前序遍历

栈-N144-二叉树的前序遍历

作者: 三次元蚂蚁 | 来源:发表于2019-03-30 12:28 被阅读0次

    题目

    思路

    • 前序遍历的顺序是根->左子树->右子树
    • 由于访问完左子树后要访问右子树,所以要先把右子树的信息暂存,所以考虑用栈实现
    • 根节点入栈
    • 重复将栈顶元素出栈直至栈为空
    1. 栈顶元素有右孩子,将右孩子入栈
    2. 栈顶元素有左孩子,将左孩子入栈

    代码

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

    相关文章

      网友评论

          本文标题:栈-N144-二叉树的前序遍历

          本文链接:https://www.haomeiwen.com/subject/mvpjbqtx.html