自下而上的树遍历

Question

如果您能向我解释如何遍历这棵树(最好使用javascript)，我将非常感激：

​

​

按以下顺序排列: 1-3-8连4-6-3-8连7-6-3-8

模拟的数据可以如下所示：

let tree = {
  'parent': {
    'immediate child': {
      'post immediate child'
    }
    'second immediate child': {
      'second post immediate child'
    }
  }
}

function goUpTheTree(tree) {

}

任何帮助都将不胜感激..。

Answer 1

基本上，您可以存储节点的路径，如果发现节点没有任何左或右分支，则以路径作为值。

​

function getBottomUp(node, path) {
    path = [node.value].concat(path || []);
    if (!node.left && !node.right) {
        console.log(JSON.stringify(path));
        return;
    }
    node.left && getBottomUp(node.left, path);
    node.right && getBottomUp(node.right, path);
}

var tree = { value: 8, left: { value: 3, left: { value: 1 }, right: { value: 6, left: { value: 4 }, right: { value: 7 } } }, right: { value: 10, right: { value: 14, left: { value: 3 } } } };

getBottomUp(tree);

​

Answer 2

你仍然可以从上到下穿过这棵树.只需记住在您的途中的节点，当您到达一个叶节点，输出所有这些节点反向。

​

var tree = 	{
	"value": 8,
	"left": {
		"value": 3,
		"left": {
			"value": 1,
			"left": null,
			"right": null
		},
		"right": {
			"value": 6,
			"left": {
				"value": 4,
				"left": null,
				"right": null
			},
			"right": {
				"value": 7,
				"left": null,
				"right": null
			}
		}
	},
	"right": {
		"value": 10,
		"left": null,
		"right": {
			"value": 14,
			"left": {
				"value": 13,
				"left": null,
				"right": null
			},
			"right": null
		}
	}
}

function goUpTheTree(node, pathFromRoot) {
    //add the current node to the path
	pathFromRoot.push(node.value);
	if(node.left == null && node.right == null) {
		//this is a leaf node
		//print the path in reverse
		pathString = "";
		pathFromRoot.forEach(function(element) { pathString = element + " " + pathString; });
		console.log(pathString);
	}
	if(node.left != null)
		goUpTheTree(node.left, pathFromRoot);
	if(node.right != null)
		goUpTheTree(node.right, pathFromRoot);
    //remove the current node from the path
	pathFromRoot.pop();
}

goUpTheTree(tree, []);

​

我使树结构更加结构化(即每个节点都有.value、.left和.right)。但基本上和你的定义是一样的。