Leetcode日记— 94.Binary Tree Inorder Traversal(本质还是树的遍历)

发布于 2020-09-26  115 次阅读


碎碎念:这篇文章是用iPad写的,有了terminus以后iPad可以ssh了,写leetcode也需要ide,似乎以后出门可以不需要带电脑了。

题目如下:

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

Example 1:

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


Example 2:

Input: root = []
Output: []


Example 3:

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


Example 4:

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


Example 5:

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

思路:

其实这题就是普通的🌲的遍历,不过正好通过这道题来复习一下树的遍历。

首先是递归做法:

递归主要考虑的是1⃣️循环停止的条件2⃣️确定函数的参数和返回值,递归来说一般都是要把某个参数传进去进行改变后再传出来。3⃣️每层递归的逻辑

就本题来说:1⃣️必然是当本层的节点值为null了就说明递归结束了。2⃣️每次传进去的就是存着遍历结果的容器3⃣️逻辑就是按照前序中序和后序分别先取中,左,右节点的值。

(以中序为例)代码如下:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

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

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

那么迭代的方法其实就是把递归时隐性维护的栈写出来进行维护罢了。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

不过前序遍历因为第一个处理当前节点,所以代码更简洁一些:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右(空节点不入栈)
            if (node->left) st.push(node->left);             // 左(空节点不入栈)
        }
        return result;
    }
};

作者:carlsun-2
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/che-di-chi-tou-er-cha-shu-de-qian-zhong-hou-xu-d-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

当然,对于中序遍历还有一种莫里森遍历,可以让空间复杂度变为O(1),但是遍历次数会变成2n。

其原理就是把每个节点左子树的最右边,也就是该节点的前序节点的右孩子指向该节点,这样就不需要维护一个栈也可以知道后面需要去哪儿了。

代码如下:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        TreeNode predecessor = null;

        while (root != null) {
            if (root.left != null) {
                // predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }
                
                // 让 predecessor 的右指针指向 root,继续遍历左子树
                if (predecessor.right == null) {
                    predecessor.right = root;
                    root = root.left;
                }
                // 说明左子树已经访问完了,我们需要断开链接
                else {
                    res.add(root.val);
                    predecessor.right = null;
                    root = root.right;
                }
            }
            // 如果没有左孩子,则直接访问右孩子
            else {
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

你好哇!欢迎来到雷公马碎碎念的地方:)