颜色标记法-一种通用且简明的树遍历方法 - 二叉树的中序遍历 - 力扣（LeetCode）

颜色标记法-一种通用且简明的树遍历方法

henryL5

发布于 2019-09-0489.3k精选Python3

官方题解中介绍了三种方法来完成树的中序遍历，包括：

在树的深度优先遍历中（包括前序、中序、后序遍历），递归方法最为直观易懂，但考虑到效率，我们通常不推荐使用递归。

栈迭代方法虽然提高了效率，但其嵌套循环却非常烧脑，不易理解，容易造成“一看就懂，一写就废”的窘况。而且对于不同的遍历顺序（前序、中序、后序），循环结构差异很大，更增加了记忆负担。

因此，我在这里介绍一种“颜色标记法”（瞎起的名字……），兼具栈迭代方法的高效，又像递归方法一样简洁易懂，更重要的是，这种方法对于前序、中序、后序遍历，能够写出完全一致的代码。

其核心思想如下：

使用这种方法实现的中序遍历如下：

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node is None: continue
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res

如要实现前序、后序遍历，只需要调整左右子节点的入栈顺序即可。

下一篇：动画演示+三种实现 94. 二叉树的中序遍历

请先后发表评论

精选评论(5)

2020-05-24

解释一下为什么需要“右子节点、自身、左子节点依次入栈”

我们有一棵二叉树：

               中
              /  \
             左   右

前序遍历：中，左，右
中序遍历：左，中，右
后序遍历：左，右，中

本题需要中序遍历。

栈是一种 先进后出的结构，出栈顺序为左，中，右
那么入栈顺序必须调整为倒序，也就是右，中，左

同理，如果是前序遍历，入栈顺序为 右，左，中；后序遍历，入栈顺序中，右，左

2019-12-18

大佬的方法还可以优化：
white对应TreeNode数据类型，gray对应int数据类型，所以不需要额外的颜色标记：

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack,rst = [root],[]
        while stack:
            i = stack.pop()
            if isinstance(i,TreeNode):
                stack.extend([i.right,i.val,i.left])
            elif isinstance(i,int):
                rst.append(i)
        return rst

（编辑过）2020-02-04

空间换时间×

空间换智商√

2019-10-05

用Java实现了一下。。。

class Solution {
    class ColorNode {
        TreeNode node;
        String color;
        
        public ColorNode(TreeNode node,String color){
            this.node = node;
            this.color = color;
        }
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<Integer>();
            
        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();
        stack.push(new ColorNode(root,"white"));
        
        while(!stack.empty()){
            ColorNode cn = stack.pop();
            
            if(cn.color.equals("white")){
                if(cn.node.right != null) stack.push(new ColorNode(cn.node.right,"white"));
                stack.push(new ColorNode(cn.node,"gray"));
                if(cn.node.left != null)stack.push(new ColorNode(cn.node.left,"white"));
            }else{
                res.add(cn.node.val);
            }
        }
        
        return res;
    }
}

2019-10-16

能够看得懂楼主方法，看其他的用栈写的让自己感觉自己就是个傻子，感谢楼主

2021-03-15

其实这种方法的本质是每个节点都要入栈两次后才能访问其元素值，第一次入栈是不能访问其值的，因为第一次入栈是第一次访问该节点，需要先访问该节点的左子树，这时会把该结点和左子树都入栈，所以第二次出栈就可以访问该结点的值啦

2021-09-02

补充一个介于楼主大佬和评论区大佬之间的折中方案，在某些情况下可能通用性会比评论区大佬的好一点点

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        is_visited = []
        stack = [root]
        while stack:
            node = stack.pop()
            if not node:
                continue
            if node not in is_visited:
                stack.extend([node.right, node, node.left])
                is_visited.append(node)
            else:
                result.append(node.value)
        return result

2020-09-14

用C++ 实现了下

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<pair<TreeNode*, int> > stk;
        stk.push((make_pair(root, 0)));
        
        while(!stk.empty()) {
            auto [node, type] = stk.top();
            stk.pop();
            if(node == nullptr) continue;
            if(type == 0) {
                stk.push(make_pair(node->right, 0));
                stk.push(make_pair(node, 1));
                stk.push(make_pair(node->left, 0));
            }
            else result.emplace_back(node->val);
        }

        return result;

    }
};

2020-07-04

补一个java版的解。这个题解的宗旨就是使用一个颜色或者任何东西，记录节点的访问次数。在中序中，节点第二次访问会被输出。因此使用颜色，或者hash表来记录节点的访问次数，次数使用hash表来记录

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {

        HashMap<TreeNode, Integer> map = new HashMap<>();
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;   //初始检查
        stack.push(root);
        map.put(root,1);//1表示第一次访问,2表示第二次访问。

        while (!stack.isEmpty())
        {
            //弹栈
            TreeNode node = stack.pop();

            //如果是第一次访问的话，则将其右子节点，自身，左子结点入栈
            if (1==map.get(node)) 
            {
                //将右子节点入栈
                if(node.right!=null)
                {
                    stack.push(node.right);
                    map.put(node.right,1);
                }
                //将自身入栈，改变访问次数
                stack.push(node);
                map.put(node,2);    //更新访问次数

                //将左子节点入栈
                if(node.left!=null)
                {
                    stack.push(node.left);
                    map.put(node.left,1);
                }

            }else {     //else表示是第2次访问，就输出
                list.add(node.val);
            }
        }
        return  list;
    }
}

（编辑过）2019-10-13

楼主的方法记忆很方便，前，中，后，层次遍历都可以统一起来，思路和时间与内存占用似乎和递归差不多？补充一下层次遍历的，加个level即可。

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        WHITE, GRAY = 0, 1
        stack = []
        init_level = 0
        stack.append((root, WHITE, init_level))
        result = []
        while stack:
            node, color, level = stack.pop()
            if node:
                if color == WHITE:
                    stack.append((node.right, WHITE, level+1))
                    stack.append((node.left, WHITE, level+1))
                    stack.append((node, GRAY, level))
                else:
                    if len(result) == level: result.append([])
                    result[level].append(node.val)
        return result

2019-10-14

好办法，用c++实现了一下

class Solution {
	vector<int>ans;
public:
	vector<int> inorderTraversal(TreeNode* root) {
		int white = 0;
		int gray = 1;
		stack<pair<int, TreeNode*>>s;
		s.push(make_pair(white,root));
		while (!s.empty())
		{
			int color = s.top().first;
			TreeNode* t = s.top().second;
			s.pop();
			if (t == NULL) continue;
			if (color == white)
			{
				s.push(make_pair(white, t->right));
				s.push(make_pair(gray, t));
				s.push(make_pair(white, t->left));
			}
			else ans.push_back(t->val);
		}
		return ans;
	}
};

2019-11-18

但是这样的话，每个元素都会有两次出入栈，是不是反而更耗时了？

2021-02-08

好办法，java实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<ColorNode> stack = new Stack();
        ColorNode rootColorNode = new ColorNode(true,root);
        stack.push(rootColorNode);
        List<Integer> res = new LinkedList<>();

        while(!stack.isEmpty()){
            ColorNode popedColorNode = stack.pop();
            TreeNode popedNode = popedColorNode.node;
            if(popedNode == null) continue;

            if(popedColorNode.firstTime){
                stack.push(new ColorNode(true,popedNode.right));
                stack.push(new ColorNode(false,popedNode));
                stack.push(new ColorNode(true,popedNode.left));
            }else {
                res.add(popedNode.val);
            }
        }
        return res;
    }

    class ColorNode{
        public boolean firstTime;
        public TreeNode node;

        public ColorNode(boolean firstTime,TreeNode node){
            this.firstTime = firstTime;
            this.node = node;
        }
    }
}

2019-12-17

思路很清楚，本质上还是递归，只是手动维护了一个调用栈，照着用JavaScript实现了一下：

/**
 * @description 使用带有访问标志的栈来模拟递归
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const [WHITE, GRAY] = [0, 1]; // WHITE - 未访问的新结点； GRAY - 已访问的结点
    const res = [];
    const stack = [[WHITE, root]];
    let color, node;
    while (stack.length) {
        [color, node] = stack.pop(); // 若栈中有元素，则按照左节点、根节点、右节点的顺序依次弹出元素
        if (!node) continue;
        if (color === WHITE) {
            // 当前指向的结点是未访问过的结点，将其右节点，根节点，左节点依次入栈
            stack.push([WHITE, node.right]);
            stack.push([GRAY, node]);
            stack.push([WHITE, node.left]);
        } else res.push(node.val);
    }
    return res;
};

颜色标记法-一种通用且简明的树遍历方法

颜色标记法-一种通用且简明的树遍历方法

Recommend

Rackspace发布第三季度财报多云业务增长势头稳健

MrBird

Personalization: Tips for building a human experience

加筑技术的“围栏”，农牧业也能高效又绿色

绿地控股转行基建，尝试“直播”等新型营销模式及渠道

Gartner：“业务可组合性”的企业才能更好应对不确定性

北交所开市后三企接受机构调研，思考私募基金调研两企

Nvidia发布第三季度财报数据中心芯片销售额大幅增长55%

星巴克两大标志性举措推动数字化转型

亏本大甩卖！中国奥园出售香港物业回血9亿港元偿债

About Joyk