讨论/《二叉树》 - 二叉树的中序遍历/
《二叉树》 - 二叉树的中序遍历
共 21 个回复

1,递归解法

下面随便画个二叉树的图。

image.png

二叉树的中序遍历顺序是:左子树→根节点→右子树

所以上图前序遍历的结果是:D→B→E→A→F→C

访问顺序如下

image.png

代码很简单

 public void inOrderTraversal(TreeNode node) {
        if (node == null)
            return;
        inOrderTraversal(node.left);
        System.out.println(node.val);
        inOrderTraversal(node.right);
    }

但这题不是让打印二叉树的节点值,而是返回一个list对象,这也很简单,我们随便改一下就行了,当然修改的方式有很多,我们随便写一个来看一下

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

    public void inOrderTraversal(TreeNode root, List<Integer> res) {
        if (root == null)
            return;
        //先打印左子树,然后打印当前节点,最后再打印右子树
        inOrderTraversal(root.left, res);
        res.add(root.val);
        inOrderTraversal(root.right, res);
    }

看一下运行结果

image.png


2,非递归解法

非递归我们使用一个栈就行了,我们来看下

    public void inOrderTraversal(TreeNode tree) {
        Stack<TreeNode> stack = new Stack<>();
        while (tree != null || !stack.isEmpty()) {
            while (tree != null) {
                stack.push(tree);
                tree = tree.left;
            }
            if (!stack.isEmpty()) {
                tree = stack.pop();
                System.out.println(tree.val);
                tree = tree.right;
            }
        }
    }

我们来改一下

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        //加个边界条件判断
        if (root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (!stack.isEmpty()) {
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }


3,Morris中序遍历方式

Morris中序遍历详细可以看下《二叉树的Morris中序和前序遍历》,这是我之前写的,由于东西太多,这里就不在照搬过来,我们直接看下莫里斯中序遍历的代码

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    //首先把根节点赋值给cur
    TreeNode cur = root;
    //如果cur不为空就继续遍历
    while (cur != null) {
        if (cur.left == null) {
            //如果当前节点cur的左子节点为空,就访问当前节点cur,
            //接着让当前节点cur指向他的右子节点
            res.add(cur.val);
            cur = cur.right;
        } else {
            TreeNode pre = cur.left;
            //查找pre节点,注意这里有个判断就是pre的右子节点不能等于cur
            while (pre.right != null && pre.right != cur)
                pre = pre.right;
            //如果pre节点的右指针指向空,我们就让他指向当前节点cur,
            //然后当前节点cur指向他的左子节点
            if (pre.right == null) {
                pre.right = cur;
                cur = cur.left;
            } else {
                //如果pre节点的右指针不为空,那么他肯定是指向cur的,
                //表示cur的左子节点都遍历完了,我们需要让pre的右
                //指针指向null,目的是把树给还原,然后再访问当前节点
                //cur,最后再让当前节点cur指向他的右子节点。
                pre.right = null;
                res.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return res;
}

来看一下运行结果

image.png


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

4
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            TreeNode p = stack.pop();
            result.add(p.val);
            root = p.right;
        }
        return result;
    }
3
function inorderTraversal(root: TreeNode | null): number[] {
    if (!root) {
        return [];
    }

    const result: number[] = [];
    const stack: TreeNode[] = [];

    while(root !== null || stack.length > 0) {
        while(root) {
            stack.push(root);
            root = root.left;
        }

        const pop = stack.pop();
        result.push(pop.val);
        root = pop.right;
    }

    return result;
};
2
  1. 迭代版
class Solution 
{
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        stack<TreeNode*> s;
        while(1)
        {
            GoAlongLeft(root, s);
            if(s.empty())
                break;
            root = s.top();
            s.pop();
            result.push_back(root->val);
            root = root -> right;
        }
        return result;
    }
    void GoAlongLeft(TreeNode *root, stack<TreeNode*> &s)
    {
        while(root)
        {
            s.push(root);
            root = root->left;
        }
    }
};
  1. 递归版
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        inoder(root, result);
        return result;
    }
    void inoder(TreeNode *root, vector<int> &res)
    {
        if(!root)
            return;
        inoder(root->left, res);
        res.push_back(root->val);
        inoder(root->right, res);
    }
};
2

解题思路

递归法。中序遍历,根节点在中间。 左-根-右。
时间复杂度O(n),空间复杂度O(n)。

/**
 * 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 {
    List<Integer> result = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root==null){
            return result;
        }
        inorderTraversal(root.left);
        result.add(root.val);
        inorderTraversal(root.right);
        return result;
    }
}
2
var inorderTraversal = function(root) {
    let res = [];
    let stack = [];
    while (stack.length > 0 || root !== null) {
        while(root !== null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop()
        res.push(root.val);
        root = root.right;
    }
    return res;
};
1

C++中序遍历递归写法:

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        dfs(root,ret);  // 中序遍历递归函数,左 根 右
        return ret;
    }
    void dfs(TreeNode* root, vector<int>& ret){
        if(root == nullptr){
            return;
        }
        dfs(root->left, ret);           // 左
        ret.push_back(root->val);       // 根
        dfs(root->right, ret);          // 右
    }

C++中序遍历非递归写法:

 vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* p = root;
        stack<TreeNode*>stack;
        vector<int> ret;
        if(root != nullptr){
            while(!stack.empty() || p != nullptr){  // 栈不为空或者树还没有遍历完
                if(p != nullptr){       // 扫描结点p的所有左下结点并进栈
                    stack.push(p);      // 一颗树的左边界进栈,左孩子结点进栈
                    p = p->left;
                }else{
                    p = stack.top();    // 弹出结点,并记录结点值
                    stack.pop();
                    ret.push_back(p->val);

                    p = p->right;       // 处理右子树
                }
            }
        }
        return ret;
    }
1

public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
List<TreeNode> pendingNodes = new ArrayList<>();
pendingNodes.add(root);
TreeNode node = null;
while (true) {
int size = pendingNodes.size();
if (size > 0) {
node = pendingNodes.remove(size - 1);
if (node == null) {
continue;
} else {
if (node.left == null) {
result.add(node.val);
pendingNodes.add(node.right);
} else {
TreeNode leftNode = node.left;
node.left = null;
pendingNodes.add(node);
pendingNodes.add(leftNode);
}
}
} else {
break;
}
}
return result;
}

1

大佬们帮忙看看这段代码有什么问题
这是错误提示,老改不对看😭

Line 28: Char 29: runtime error: member access within null pointer of type 'TreeNode' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:37:29
print('Hello world!')
puts 'Hello world!'
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> num;
        vector<int> l;
        vector<int> r;
        if(root !=nullptr)
        {
            if(root->left != nullptr)
            {
                l=inorderTraversal(root->left);
                num.insert(num.end(),l.begin(),l.end());
            }
        }
        num.push_back(root->val);
        if(root != nullptr)
        {
            if(root->right != nullptr)
            {
                r=inorderTraversal(root->right);
                num.insert(num.end(),r.begin(),r.end());
            }
        }
        return num;
    }
};

Java递归实现

public void travel(TreeNode t, List<Integer> l1){
        if(t==null){
            return;
        }
        travel(t.left, l1);
        l1.add(t.val);
        travel(t.right, l1);
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>  l1 = new ArrayList<Integer> ();
        travel(root, l1);
        return l1;
    }

Java非递归实现(栈)

public List<Integer> inorderTraversal(TreeNode root) {
        List l1 = new ArrayList();
        if(root==null)
           return l1;
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        //
        while(!s1.empty()||root!=null){
            // 如果栈顶结点左孩子存在,则左孩子压栈
            // 第一轮循环时直接判断根结点左孩子存在,存在就压栈,循环到栈顶结点没有左孩子为止
            // 后面的循环中只要出栈的结点没有右孩子就不会进行循环,直接进行下面的出栈了
            while(root!=null){
                s1.push(root);
                root = root.left;
            }
            if(!s1.empty()){
                // 出栈并输出栈顶结点,root再记录输出的栈顶结点的右孩子
                // 如果右孩子存在,下一轮循环会将其压栈
                // 如果右孩子不存在,下一轮循环就没有压栈操作,继续出栈(栈不空)
                root = s1.pop();
                l1.add(root.val);
                root = root.right;
            }
        }
        return l1;
    }

Morris算法(java实现)

    public List<Integer> inorderTraversal(TreeNode root) {
        List l1 = new ArrayList();
        TreeNode cur = root;
        while(cur!=null){
            if(cur.left == null){
                l1.add(cur.val);
                cur = cur.right;
            }else{
                TreeNode pre = cur.left;
                // 找到cur的左子节点的最右子结点
                // 
                while(pre.right!=null&&pre.right!=cur)
                   pre = pre.right;
                // 如果没有找到则直接将左节点的右子节点指向cur
                if(pre.right==null){
                    pre.right = cur;
                    cur = cur.left;
                }else{
                // 如果pre.right不为空,那么塔肯定指向cur
                // 直接输出cur并且将cur指向cur的右子节点
                    pre.right = null;
                    l1.add(cur.val);
                    cur = cur.right;
                }
            }
        }
        return l1;
    }